Degree-Constrained Subgraph Problems: Hardness and Approximation Results
DOI10.1007/978-3-540-93980-1_3zbMATH Open1209.68629OpenAlexW1596627253MaRDI QIDQ3602827FDOQ3602827
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
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
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)
Cites Work
- Matching theory
- Degree constrained subgraphs
- Succinct representation of balanced parentheses and static trees
- Finding a Path of Superlogarithmic Length
- The dense \(k\)-subgraph problem
- On approximating the longest path in a graph
- The number of trees
- The Traveling Salesman Problem with Distances One and Two
- On the hardness of approximating minimization problems
- Title not available (Why is that?)
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
- Degree-Constrained Subgraph Problems: Hardness and Approximation Results
- Subgraphs of minimal degree \(k\)
- Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract)
- Approximation algorithms for degree-constrained minimum-cost network-design problems
- Hardness and Approximation of Traffic Grooming
Cited In (19)
- Parameterized domination in circle graphs
- On dynamic monopolies of graphs with general thresholds
- The maximum binary tree problem
- Title not available (Why is that?)
- 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)
