On approximating the d-girth of a graph

DOI10.1016/J.DAM.2013.04.022MaRDI QIDQ2444552zbMATH OpenOpenAlexFDO

Authors David Peleg, Ignasi Sau, Mordechai Shalom

Publication date 10 April 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2013.04.022

zbMATH Keywords

randomized algorithmapproximation algorithmminimum degreeplanar graphhardness of approximationgeneralized girth

Mathematics Subject Classification ID

Randomized algorithms (68W20) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07) Paths and cycles (05C38)

Recommendations

• On Approximating the d-Girth of a Graph
• scientific article; zbMATH DE number 7053319
• scientific article; zbMATH DE number 1670873
• Parameterized complexity of finding small degree-constrained subgraphs

Cites work

• scientific article; zbMATH DE number 4073016 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1754610 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• 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
• Dynamic programming for graphs on surfaces
• Hardness and approximation of traffic grooming
• 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
• On the approximability of some degree-constrained subgraph problems
• On the complexity of approximating the independent set problem
• Parameterized complexity of finding small degree-constrained subgraphs
• Planar subgraph isomorphism revisited
• Subgraphs of minimal degree \(k\)
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The ring grooming problem

Cited in

(5)

• scientific article; zbMATH DE number 1953179 (Why is no real title available?)
• On Approximating the d-Girth of a Graph
• Minimum k‐cores and the k‐core polytope
• 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 Q2444552)