Degree-Constrained Subgraph Problems: Hardness and Approximation Results

DOI10.1007/978-3-540-93980-1_3MaRDI QIDQ3602827zbMATH OpenOpenAlexFDO

Authors Omid Amini, Stéphane Pérennes, Ignasi Sau, 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 approximationexcluded minorPTASAPXdegree-constrained subgraphs

Mathematics Subject Classification ID

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

Recommendations

• On the approximability of some degree-constrained subgraph problems
• Linear time approximation algorithms for~degree~constrained subgraph problems
• A note on degree-constrained subgraphs
• Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
• Parameterized complexity of finding small degree-constrained subgraphs
• Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
• Degree constrained subgraphs
• Degree-constrained subgraph reconfiguration is in P
• On the complexity of some subgraph problems
• scientific article; zbMATH DE number 1101952

Cites work

• scientific article; zbMATH DE number 742978 (Why is no real title available?)
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract)
• Degree constrained subgraphs
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Finding a Path of Superlogarithmic Length
• Hardness and Approximation of Traffic Grooming
• Matching theory
• On approximating the longest path in a graph
• On the hardness of approximating minimization problems
• Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
• Subgraphs of minimal degree \(k\)
• Succinct representation of balanced parentheses and static trees
• The Traveling Salesman Problem with Distances One and Two
• The dense \(k\)-subgraph problem
• The number of trees

Cited in

(19)

• Parameterized domination in circle graphs
• On dynamic monopolies of graphs with general thresholds
• The maximum binary tree problem
• scientific article; zbMATH DE number 1859295 (Why is no real title available?)
• Constant factor approximation for the weighted partial degree bounded edge packing problem
• An ILP formulation and genetic algorithm for the maximum degree-bounded connected subgraph problem
• On Approximating the d-Girth of a Graph
• Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
• Partial degree bounded edge packing problem with arbitrary bounds
• Tight complexity bounds for FPT subgraph problems parameterized by clique-width
• Degree constrained subgraphs
• Subexponential parameterized algorithms for bounded-degree connected subgraph problems on planar graphs
• Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
• On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• The maximum degree \& diameter-bounded subgraph and its applications
• The Maximum Binary Tree Problem.
• Parameterized complexity of finding small degree-constrained subgraphs
• On the approximability of some degree-constrained subgraph problems

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

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