On Approximating the d-Girth of a Graph

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

Ignasi Sau, Mordechai Shalom, David Peleg

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 algorithmrandomized algorithmminimum degreeplanar graphhardness of approximationgeneralized girth

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

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

Cites Work

• 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
• Planar Subgraph Isomorphism Revisited
• 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

This page was built for publication: On Approximating the d-Girth of a Graph