Combinatorial network abstraction by trees and distances

DOI10.1016/j.tcs.2008.03.037zbMath1152.68042MaRDI QIDQ954979

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

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

zbMATH Keywords

NP-completeness; matrix norms; inapproximability; spanning trees; network abstraction

Mathematics Subject Classification ID

05C05: Trees

05C35: Extremal problems in graph theory

68R10: Graph theory (including graph drawing) in computer science

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C12: Distance in graphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Cites Work

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