Combinatorial network abstraction by trees and distances
DOI10.1016/j.tcs.2008.03.037zbMath1152.68042OpenAlexW1982160332MaRDI QIDQ954979
Hanjo Täubig, Stefan Eckhardt, Sven Kosub, Sebastian Wernicke, Moritz G. Maaß
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
Trees (05C05) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
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
This page was built for publication: Combinatorial network abstraction by trees and distances
