On the approximability of some degree-constrained subgraph problems

DOI10.1016/j.dam.2012.03.025zbMath1246.05040OpenAlexW1975573070MaRDI QIDQ444431

Stéphane Pérennes, Ignasi Sau, Saket Saurabh, Omid Amini, David Peleg

Publication date: 14 August 2012

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

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

zbMATH Keywords

approximation algorithmshardness of approximationdegree-constrained subgraph

Mathematics Subject Classification ID

Approximation algorithms (68W25) Vertex degrees (05C07) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ Minimum k‐cores and the k‐core polytope ⋮ Effective and efficient community search with size constraint on bipartite graphs ⋮ On approximating the \(d\)-girth of a graph ⋮ Distributed backup placement in networks ⋮ On robust clusters of minimum cardinality in networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of finding small degree-constrained subgraphs
• On approximating the longest path in a graph
• Minimum vertex weighted deficiency of \((g,f)\)-factors: A greedy algorithm
• Subgraphs of minimal degree \(k\)
• Hardness and approximation of traffic grooming
• Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
• Matching theory
• On a connection between the existence of k-trees and the toughness of a graph
• Long cycles in graphs with no subgraphs of minimal degree 3
• Another look at the degree constrained subgraph problem
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Degree constrained subgraphs
• The number of trees
• Succinct Representation of Balanced Parentheses and Static Trees
• Color-coding
• Detecting high log-densities
• Induced Subgraphs of the Power of a Cycle
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Finding a Path of Superlogarithmic Length
• The Traveling Salesman Problem with Distances One and Two
• On the hardness of approximating minimization problems
• Finding Paths and Cycles of Superpolylogarithmic Length
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The dense \(k\)-subgraph problem
• Approximation algorithms for degree-constrained minimum-cost network-design problems