On approximating the d-girth of a graph

DOI10.1016/J.DAM.2013.04.022zbMATH Open1285.05041OpenAlexW2086867223MaRDI QIDQ2444552FDOQ2444552

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

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

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)

Cites Work

• Degree constrained subgraphs
• Approximation algorithms for NP-complete problems on planar graphs
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Title not available (Why is that?)
• On approximating the longest path in a graph
• A Separator Theorem for Planar Graphs
• Title not available (Why is that?)
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On the complexity of approximating the independent set problem
• A Census of Planar Triangulations
• Approximating Directed Weighted-Degree Constrained Networks
• Parameterized complexity of finding small degree-constrained subgraphs
• On the approximability of some degree-constrained subgraph problems
• Planar subgraph isomorphism revisited
• Subgraphs of minimal degree \(k\)
• Long cycles in graphs with no subgraphs of minimal degree 3
• Induced Subgraphs of the Power of a Cycle
• Title not available (Why is that?)
• The ring grooming problem
• Hardness and approximation of traffic grooming
• Dynamic programming for graphs on surfaces
• Title not available (Why is that?)
• A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs
• On Approximating the d-Girth of a Graph

Cited In (5)

• Title not available (Why is that?)
• 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)