Minimum t-spanners on subcubic graphs

DOI10.1007/978-3-030-96731-4_30MaRDI QIDQ2154116zbMATH OpenOpenAlexFDO

Authors Renzo Gómez, Flávio K. Miyazawa, Yoshiko Wakabayashi

Publication date 13 July 2022

Full work available at URL https://doi.org/10.1007/978-3-030-96731-4_30

zbMATH Keywords

polyhedraspannersubcubic graphtree spannersparse spanner

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A trade-off between space and efficiency for routing tables
• An Optimal Synchronizer for the Hypercube
• Approximate distance oracles
• Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time
• Edge tree spanners
• Generating Sparse 2-Spanners
• Graph spanners
• Graph spanners: a tutorial review
• Graph structure and monadic second-order logic. A language-theoretic approach
• Linear Programming
• NP-completeness of minimum spanner problems
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• On sparse spanners of weighted graphs
• On the hardness of approximating spanners
• Optimality computation of the minimum stretch spanning tree problem
• Restrictions of minimum spanner problems
• Spanners in graphs of bounded degree
• Spanners of bounded degree graphs
• The hardness of approximating spanner problems
• Tree Spanners
• Tree spanners in planar graphs
• Tree spanners of bounded degree graphs

Cited in

(3)

• Tree 3-spanners on generalized prisms of graphs
• Polynomial algorithms for sparse spanners on subcubic graphs
• Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs

This page was built for publication: Minimum \(t\)-spanners on subcubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2154116)