On approximation properties of the Independent set problem for degree 3 graphs
From MaRDI portal
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Recommendations
- On approximation properties of the independent set problem for low degree graphs
- Structural Information and Communication Complexity
- scientific article; zbMATH DE number 1003268
- Improved approximations of independent sets in bounded-degree graphs
- On the complexity of approximating the independent set problem
Cites work
- Approximation algorithms for NP-complete problems on planar graphs
- Efficient bounds for the stable set, vertex cover and set packing problems
- Greed is good: approximating independent sets in sparse and bounded-degree graphs
- scientific article; zbMATH DE number 1003266 (Why is no real title available?)
- scientific article; zbMATH DE number 1003268 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 3043302 (Why is no real title available?)
- Improved approximations of independent sets in bounded-degree graphs
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- On Syntactic versus Computational Views of Approximability
- Optimization, approximation, and complexity classes
- Some simplified NP-complete graph problems
- Three short proofs in graph theory
- Vertex packings: Structural properties and algorithms
Cited in
(35)- Reversal and transposition medians
- Priority algorithms for graph optimization problems
- On the complexity of approximating the independent set problem
- On approximation properties of the independent set problem for low degree graphs
- Local approximations for maximum partial subgraph problem.
- Some APX-completeness results for cubic graphs
- The quadratic shortest path problem: complexity, approximability, and solution methods
- Conversion of coloring algorithms into maximum weight independent set algorithms
- Improved approximation algorithms for path vertex covers in regular graphs
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- On the complexity of the independent set problem in triangle graphs
- Approximability of the upper chromatic number of hypergraphs
- The maximum clique problem in multiple interval graphs
- Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
- Maximum independent sets in graphs of low degree
- Approximation algorithm for the distance-3 independent set problem on cubic graphs
- scientific article; zbMATH DE number 1003268 (Why is no real title available?)
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
- On the complexity of approximating the independent set problem (extended abstract)
- Structural Information and Communication Complexity
- When polynomial approximation meets exact computation
- Inapproximability results for bounded variants of optimization problems.
- When polynomial approximation meets exact computation
- Minus domination in small-degree graphs
- On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows
- Improved non-approximability results for vertex cover with density constraints
- Forest covers
- On the complexity of finding 1-center spanning trees
- Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs
- Using fractional primal-dual to schedule split intervals with demands
- A note on the precedence-constrained class sequencing problem
- The longest common subsequence problem for arc-annotated sequences
- Simultaneous matchings: Hardness and approximation
This page was built for publication: On approximation properties of the Independent set problem for degree 3 graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5057456)
