Minimum \(t\)-spanners on subcubic graphs
From MaRDI portal
Publication:2154116
DOI10.1007/978-3-030-96731-4_30OpenAlexW4225639063MaRDI QIDQ2154116
Yoshiko Wakabayashi, Renzo Gómez, Flávio K. Miyazawa
Publication date: 13 July 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-96731-4_30
Related Items
Tree 3-spanners on generalized prisms of graphs, Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs
Cites Work
- Unnamed Item
- On sparse spanners of weighted graphs
- NP-completeness of minimum spanner problems
- Restrictions of minimum spanner problems
- Tree spanners of bounded degree graphs
- NP-hardness and fixed-parameter tractability of the minimum spanner problem
- Spanners of bounded degree graphs
- Graph spanners: a tutorial review
- Edge tree spanners
- The hardness of approximating spanner problems
- Optimality computation of the minimum stretch spanning tree problem
- Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
- Approximate distance oracles
- Graph spanners
- Spanners in graphs of bounded degree
- Generating Sparse 2-Spanners
- Linear Programming
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Tree Spanners
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Tree spanners in planar graphs
- On the hardness of approximating spanners
