Spanners in graphs of bounded degree

DOI10.1002/net.3230240406zbMath0821.68091OpenAlexW2034220466MaRDI QIDQ4303628

Mark J. Keil, Leizhen Cai

Publication date: 19 September 1995

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230240406

zbMATH Keywords

NP-completeness\(t\)-spanner

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Related Items (13)

Spanners of de Bruijn and Kautz graphs ⋮ Spanners of underlying graphs of iterated line digraphs ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ Bounds on the Spanner-Sum of Torus ⋮ Restrictions of minimum spanner problems ⋮ A PTAS for the sparsest 2-spanner of 4-connected planar triangulations ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ Minimum spanners of butterfly 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 ⋮ NP-hardness and fixed-parameter tractability of the minimum spanner problem ⋮ Edge-disjoint spanners of complete graphs and complete digraphs

Cites Work

• A generalization of line graphs: (X, Y)-intersection graphs
• Unnamed Item

This page was built for publication: Spanners in graphs of bounded degree