Approximation algorithms for finding low-degree subgraphs

DOI10.1002/net.20031zbMath1061.68184OpenAlexW1971422464MaRDI QIDQ4651931

Radha Krishnan, R. Ravi, Balaji Raghavachari, Philip N. Klein

Publication date: 23 February 2005

Published in: Networks (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsnetwork designgraph connectivityapproximation algorithmsNP-hard problemsminimum-degree subgraphs

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (7)

Spanning trees with minimum weighted degrees ⋮ On some network design problems with degree constraints ⋮ Parameterized complexity of finding small degree-constrained subgraphs ⋮ A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem ⋮ Edge ranking and searching in partial orders ⋮ Network-Design with Degree Constraints ⋮ Unnamed Item

Cites Work

• Geometric algorithms and combinatorial optimization
• Primal-dual meets local search
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximation algorithms for finding low-degree subgraphs