Combinatorial network abstraction by trees and distances
From MaRDI portal
Publication:954979
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
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