On the approximability of some degree-constrained subgraph problems
DOI10.1016/J.DAM.2012.03.025zbMATH Open1246.05040OpenAlexW1975573070MaRDI QIDQ444431FDOQ444431
Authors: Omid Amini, Stéphane Pérennes, Ignasi Sau, Saket Saurabh, 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
Recommendations
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Approximation algorithms (68W25) Vertex degrees (05C07)
Cites Work
- Title not available (Why is that?)
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Matching theory
- Optimization, approximation, and complexity classes
- Some APX-completeness results for cubic graphs
- Degree constrained subgraphs
- Succinct representation of balanced parentheses and static trees
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- Finding large cycles in Hamiltonian graphs
- Finding a Path of Superlogarithmic Length
- Title not available (Why is that?)
- Finding Paths and Cycles of Superpolylogarithmic Length
- The dense \(k\)-subgraph problem
- On approximating the longest path in a graph
- The number of trees
- Title not available (Why is that?)
- The Traveling Salesman Problem with Distances One and Two
- On the hardness of approximating minimization problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Parameterized complexity of finding small degree-constrained subgraphs
- 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?)
- Hardness and approximation of traffic grooming
- Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
- On a connection between the existence of k-trees and the toughness of a graph
- Another look at the degree constrained subgraph problem
- 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
- Minimum vertex weighted deficiency of \((g,f)\)-factors: A greedy algorithm
Cited In (13)
- Distributed backup placement in networks
- On approximating the \(d\)-girth of a graph
- An ILP formulation and genetic algorithm for the maximum degree-bounded connected subgraph problem
- Minimum k‐cores and the k‐core polytope
- On robust clusters of minimum cardinality in networks
- Target set in threshold models
- Degree constrained subgraphs
- Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
- Effective and efficient community search with size constraint on bipartite graphs
- 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
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
This page was built for publication: On the approximability of some degree-constrained subgraph problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q444431)
