Restrictions of minimum spanner problems
From MaRDI portal
Publication:1370655
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
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
