Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs

DOI10.1007/978-3-319-48749-6_20MaRDI QIDQ2958319zbMATH OpenOpenAlexFDO

Authors Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano

Publication date 1 February 2017

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-48749-6_20

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) 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

• Structural Information and Communication Complexity
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Distance-d independent set problems for bipartite and chordal graphs
• scientific article; zbMATH DE number 3881891
• On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
• The maximum distance-d independent set problem on unit disk graphs
• An approximation algorithm for the maximum independent set problem in cubic planar graphs
• On approximation properties of the independent set problem for low degree graphs
• scientific article; zbMATH DE number 1696627
• Approximation algorithms for independent sets in map graphs

Cites work

• 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
• Approximation algorithms for NP-complete problems on planar graphs
• Complexity of approximating bounded variants of optimization problems
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• scientific article; zbMATH DE number 753971 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• 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
• Smallest regular graphs of given degree and diameter
• The complexity of comparability graph recognition and coloring
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(11)

• Structurally parameterized \(d\)-scattered set
• Improved (In-)approximability bounds for \(d\)-scattered set
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Approximation algorithm for the distance-3 independent set problem on cubic graphs
• Distance-d independent set problems for bipartite and chordal graphs
• On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs
• On the complexity of distance-\(d\) independent set reconfiguration
• Improved (In-)Approximability Bounds for d-Scattered Set
• The maximum 3-star packing problem in claw-free cubic graphs
• On distance-d independent set problems for some graph classes
• Temporal reachability dominating sets: contagion in temporal graphs

This page was built for publication: Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2958319)