Restrictions of minimum spanner problems

DOI10.1006/inco.1997.2641zbMath0890.68106OpenAlexW2069409708MaRDI QIDQ1370655

M. S. Madanlal, G. Venkatesan, C. Pandu Rangan, Udi Rotics, Johann A. Makowsky

Publication date: 14 December 1997

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/783aac356a8bcc9f8b102336981044827a7bfc4f

zbMATH Keywords

\(t\)-spannertree spanners

Mathematics Subject Classification ID

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

Related Items (20)

Tree spanners on chordal graphs: complexity and algorithms ⋮ Well-partitioned chordal graphs ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ Tree spanners of bounded degree graphs ⋮ Three problems on well-partitioned chordal graphs ⋮ A linear time algorithm to construct a tree 4-spanner on trapezoid graphs ⋮ An optimal parallel algorithm to construct a tree 3-spanner on interval graphs ⋮ Network flow spanners ⋮ NP-hardness and fixed-parameter tractability of the minimum spanner problem ⋮ Hardness and approximation of minimum distortion embeddings ⋮ ON SPANNERS OF GEOMETRIC GRAPHS ⋮ The minimum stretch spanning tree problem for typical graphs ⋮ On 2-detour subgraphs of the hypercube ⋮ COMPUTING GRAPH SPANNERS IN SMALL MEMORY: FAULT-TOLERANCE AND STREAMING ⋮ Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction ⋮ Mixed-integer programming approaches for the tree \(t^*\)-spanner problem ⋮ Additive sparse spanners for graphs with bounded length of largest induced cycle

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• Tree 3-spanners on interval, permutation and regular bipartite graphs
• A unified approach to domination problems on interval graphs
• On sparse spanners of weighted graphs
• The NP-completeness of the bandwidth minimization problem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• NP-completeness of minimum spanner problems
• Parallel concepts in graph theory
• Complexity of network synchronization
• Graph spanners
• Edge Dominating Sets in Graphs
• Edge-Deletion Problems
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• Complexity Results for Bandwidth Minimization
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Spanners in graphs of bounded degree
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• A trade-off between space and efficiency for routing tables
• An Optimal Synchronizer for the Hypercube
• Grid spanners
• Additive graph spanners
• A Characterization of Comparability Graphs and of Interval Graphs
• Approximating the bandwidth for asteroidal triple-free graphs

This page was built for publication: Restrictions of minimum spanner problems