Approximation algorithm for the distance-3 independent set problem on cubic graphs
DOI10.1007/978-3-319-53925-6_18zbMATH Open1485.68312OpenAlexW2589102023MaRDI QIDQ2980912FDOQ2980912
Authors: Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano 
Publication date: 5 May 2017
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-53925-6_18
Recommendations
- Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
- An approximation algorithm for the maximum independent set problem in cubic planar graphs
- Distance-\(d\) independent set problems for bipartite and chordal graphs
- On approximation properties of the Independent set problem for degree 3 graphs
- The maximum independent set problem for cubic planar graphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Complexity of approximating bounded variants of optimization problems
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Algorithms on circular-arc graphs
- Title not available (Why is that?)
- On maximal independent sets of vertices in claw-free graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- The complexity of comparability graph recognition and coloring
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- Maximum weight independent sets in hole- and co-chair-free graphs
- On approximation properties of the independent set problem for low degree graphs
- Powers of geometric intersection graphs and dispersion algorithms
- Distance-\(d\) independent set problems for bipartite and chordal graphs
- Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
Cited In (9)
- The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices
- Distance-\(d\) independent set problems for bipartite and chordal graphs
- An approximation algorithm for the maximum independent set problem in cubic planar graphs
- Packing 2- and 3-stars into cubic graphs
- The maximum 3-star packing problem in claw-free cubic graphs
- A cubic-time algorithm for computing the trinet distance between level-1 networks
- Structurally parameterized \(d\)-scattered set
- Packing 2- and 3-stars into \(( 2 , 3 )\)-regular graphs
- Improved (In-)Approximability Bounds for d-Scattered Set
This page was built for publication: Approximation algorithm for the distance-3 independent set problem on cubic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2980912)
