Degree-Constrained Subgraph Problems: Hardness and Approximation Results

DOI10.1007/978-3-540-93980-1_3zbMath1209.68629OpenAlexW1596627253MaRDI QIDQ3602827

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

Publication date: 12 February 2009

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/inria-00331747/file/Amply_bis.pdf

zbMATH Keywords

approximation algorithmshardness of approximationPTASexcluded minorAPXdegree-constrained subgraphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (11)

Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ The maximum degree \& diameter-bounded subgraph and its applications ⋮ On dynamic monopolies of graphs with general thresholds ⋮ Parameterized complexity of finding small degree-constrained subgraphs ⋮ Parameterized domination in circle graphs ⋮ The Maximum Binary Tree Problem. ⋮ Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs ⋮ Degree-Constrained Subgraph Problems: Hardness and Approximation Results ⋮ The maximum binary tree problem ⋮ On Approximating the d-Girth of a Graph ⋮ Subexponential Parameterized Algorithms for Bounded-Degree Connected Subgraph Problems on Planar Graphs

Cites Work

• Unnamed Item
• On approximating the longest path in a graph
• Subgraphs of minimal degree \(k\)
• Matching theory
• Degree constrained subgraphs
• The number of trees
• Succinct Representation of Balanced Parentheses and Static Trees
• Color-coding
• Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• 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
• Hardness and Approximation of Traffic Grooming
• The dense \(k\)-subgraph problem
• Approximation algorithms for degree-constrained minimum-cost network-design problems

This page was built for publication: Degree-Constrained Subgraph Problems: Hardness and Approximation Results