On approximation properties of the Independent set problem for degree 3 graphs
From MaRDI portal
Publication:5057456
DOI10.1007/3-540-60220-8_84zbMath1502.68207OpenAlexW3166880264WikidataQ56335600 ScholiaQ56335600MaRDI QIDQ5057456
Toshihiro Fujito, Piotr Berman
Publication date: 16 December 2022
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-60220-8_84
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items
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 ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows ⋮ 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 ⋮ Improved non-approximability results for vertex cover with density constraints ⋮ When polynomial approximation meets exact computation ⋮ Simultaneous matchings: Hardness and approximation ⋮ When polynomial approximation meets exact computation ⋮ The quadratic shortest path problem: complexity, approximability, and solution methods ⋮ Minus domination in small-degree graphs ⋮ Improved approximation algorithms for path vertex covers in regular graphs ⋮ Conversion of coloring algorithms into maximum weight independent set algorithms ⋮ Reversal and transposition medians ⋮ Priority algorithms for graph optimization problems ⋮ Approximability of the upper chromatic number of hypergraphs ⋮ The maximum clique problem in multiple interval graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Efficient bounds for the stable set, vertex cover and set packing problems
- Optimization, approximation, and complexity classes
- Three short proofs in graph theory
- Some simplified NP-complete graph problems
- Greed is good
- Vertex packings: Structural properties and algorithms
- On Syntactic versus Computational Views of Approximability
- Approximation algorithms for NP-complete problems on planar graphs
- Improved approximations of independent sets in bounded-degree graphs
