Combinatorial network abstraction by trees and distances

DOI10.1016/J.TCS.2008.03.037zbMATH Open1152.68042OpenAlexW1982160332MaRDI QIDQ954979FDOQ954979

Authors: Stefan Eckhardt, Sven Kosub, Moritz G. Maaß, Hanjo Täubig, Sebastian Wernicke 

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://mediatum.ub.tum.de/doc/1094448/document.pdf

Recommendations

• Algorithms and Computation
• Distance Approximating Trees: Complexity and Algorithms
• The zoo of tree spanner problems
• Inapproximability and a polynomially solvable special case of a network improvement problem.
• scientific article

zbMATH Keywords

spanning treesNP-completenessinapproximabilitymatrix normsnetwork abstraction

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12)

Cites Work

• Some optimal inapproximability results
• Low complexity variants of the arrow distributed directory
• There are planar graphs almost as good as the complete graph
• Complexity of network synchronization
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Optimal Synchronizer for the Hypercube
• Tree spanners in planar graphs
• Network analysis. Methodological foundations.
• Graph spanners
• Additive graph spanners
• The centrality index of a graph
• The complexity of the network design problem
• On the minimum diameter spanning tree problem
• Title not available (Why is that?)
• Additive Tree Spanners
• Distance approximating spanning trees
• NP-completeness of minimum spanner problems
• On the hardness of approximating spanners
• MAD trees and distance-hereditary graphs
• Complexity of spanning tree problems: Part I
• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs

Cited In (4)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms and Computation
• Constructing tree-child networks from distance matrices

This page was built for publication: Combinatorial network abstraction by trees and distances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q954979)