Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
DOI10.1007/978-3-319-48749-6_20zbMath1483.68256OpenAlexW2541167211MaRDI QIDQ2958319
Zhilong Liu, Takehiro Ito, Hiroshi Eto, 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
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) 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 (3)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- 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
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Algorithms on circular-arc graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Smallest regular graphs of given degree and diameter
- 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: Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
