Combinatorial network abstraction by trees and distances

DOI10.1016/J.TCS.2008.03.037MaRDI QIDQ954979zbMATH OpenOpenAlexFDO

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

inapproximabilitymatrix normsnetwork abstractionNP-completenessspanning trees

Mathematics Subject Classification ID

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

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

• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• Additive graph spanners
• Additive Tree 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
• scientific article; zbMATH DE number 1375574 (Why is no real title available?)
• Low complexity variants of the arrow distributed directory
• MAD trees and distance-hereditary graphs
• Network analysis. Methodological foundations.
• NP-completeness of minimum spanner problems
• 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 1232244 (Why is no real title available?)
• scientific article; zbMATH DE number 6297807 (Why is no real title available?)
• 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)