Approximation algorithm for the distance-3 independent set problem on cubic graphs

DOI10.1007/978-3-319-53925-6_18MaRDI QIDQ2980912zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Algorithms on circular-arc graphs
• Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
• Complexity of approximating bounded variants of optimization problems
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Maximum weight independent sets in hole- and co-chair-free graphs
• On approximation properties of the independent set problem for low degree graphs
• On maximal independent sets of vertices in claw-free graphs
• Powers of geometric intersection graphs and dispersion algorithms
• The complexity of comparability graph recognition and coloring

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
• A cubic-time algorithm for computing the trinet distance between level-1 networks
• Packing 2- and 3-stars into cubic graphs
• The maximum 3-star packing problem in claw-free cubic graphs
• 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)