On Approximating the d-Girth of a Graph

DOI10.1007/978-3-642-18381-2_39MaRDI QIDQ3075539zbMATH OpenOpenAlexFDO

Authors 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 algorithmgeneralized girthhardness of approximationminimum degreeplanar graphrandomized algorithm

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)

Recommendations

• On approximating the \(d\)-girth of a graph
• On approximating the maximum diameter ratio of graphs
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• Towards tight approximation bounds for graph diameter and eccentricities
• scientific article; zbMATH DE number 434495
• Better approximation algorithms for the graph diameter
• An approximability-related parameter on graphs -- properties and applications
• Approximating the diameter of planar graphs in near linear time
• Approximating the Diameter of Planar Graphs in Near Linear Time
• Approximation theorems on graphs

Cites work

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

Cited in

(4)

• On approximating the \(d\)-girth of a graph
• scientific article; zbMATH DE number 1953179 (Why is no real title available?)
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• Fast and Simple Approximation of the Diameter and Radius of a Graph

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

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