Polynomial algorithms for sparse spanners on subcubic graphs
From MaRDI portal
Publication:6621853
DOI10.1007/s10878-024-01197-9MaRDI QIDQ6621853
Flávio K. Miyazawa, Renzo Gómez, Y. Wakababayashi
Publication date: 21 October 2024
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Mathematical programming (90Cxx)
Cites Work
- Title not available (Why is that?)
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- Spanners in sparse graphs
- Tree spanners for bipartite graphs and probe interval 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
- Minimum \(t\)-spanners on subcubic graphs
- Hardness and efficiency on \(t\)-admissibility for graph operations
- Mixed-integer programming approaches for the tree \(t^*\)-spanner problem
- Optimality computation of the minimum stretch spanning tree problem
- Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs
- Approximate distance oracles for unweighted graphs in expected O ( n 2 ) time
- Approximate distance oracles
- Complexity of network synchronization
- Graph spanners
- Spanners in graphs of bounded degree
- 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
- Tree 3-spanners on generalized prisms of graphs
This page was built for publication: Polynomial algorithms for sparse spanners on subcubic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6621853)
