Combinatorial network abstraction by trees and distances

DOI10.1016/J.TCS.2008.03.037MaRDI QIDQ954979zbMATHOpenAlexFDO

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

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)

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 DE number 176576

Cites work

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

Cited in

(4)

• scientific article; zbMATH DE number 6297807 (Why is no real title available?)
• scientific article; zbMATH DE number 1232244 (Why is no real title available?)
• Constructing tree-child networks from distance matrices
• Algorithms and Computation

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)