On Approximating the d-Girth of a Graph

DOI10.1007/978-3-642-18381-2_39zbMath1298.68297MaRDI QIDQ3075539

David Peleg, Mordechai Shalom, Ignasi Sau

Publication date: 15 February 2011

Published in: SOFSEM 2011: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-18381-2_39

zbMATH Keywords

approximation algorithm; randomized algorithm; minimum degree; planar graph; hardness of approximation; generalized girth

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

Related Items

On approximating the \(d\)-girth of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximating the longest path in a graph
• Subgraphs of minimal degree \(k\)
• Hardness and approximation of traffic grooming
• Long cycles in graphs with no subgraphs of minimal degree 3
• On approximating the \(d\)-girth of a graph
• Degree constrained subgraphs
• A Census of Planar Triangulations
• Induced Subgraphs of the Power of a Cycle
• Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
• Approximating Directed Weighted-Degree Constrained Networks
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• A Separator Theorem for Planar Graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Approximation algorithms for NP-complete problems on planar graphs
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• The ring grooming problem
• A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs