Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs

DOI10.1007/978-3-319-53925-6_18zbMath1485.68312OpenAlexW2589102023MaRDI QIDQ2980912

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (4)

Packing 2- and 3-stars into cubic graphs ⋮ Improved (In-)Approximability Bounds for d-Scattered Set ⋮ The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices ⋮ Structurally parameterized \(d\)-scattered set

Cites Work

• Unnamed Item
• Unnamed Item
• Maximum weight independent sets in hole- and co-chair-free graphs
• On maximal independent sets of vertices in claw-free graphs
• The complexity of comparability graph recognition and coloring
• On approximation properties of the independent set problem for low degree graphs
• Powers of geometric intersection graphs and dispersion algorithms
• Complexity of approximating bounded variants of optimization problems
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
• Algorithms on circular-arc graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs