Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
From MaRDI portal
Publication:1958629
DOI10.1007/s11590-009-0146-5zbMath1202.90257MaRDI QIDQ1958629
Svyatoslav Trukhanov, Shyam Sundar Chandramouli, Balabhaskar Balasundaram
Publication date: 4 October 2010
Published in: Optimization Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11590-009-0146-5
graph coloring; independent set; \(k\)-dependent set; defective coloring; \(t\)-improper coloring; co-\(k\)-plex
90C35: Programming involving graphs or networks
Related Items
On the Parameterized Complexity of Maximum Degree Contraction Problem., Finding maximum subgraphs with relatively large vertex connectivity, Co-2-plex vertex partitions, On bounded-degree vertex deletion parameterized by treewidth, On the parameterized complexity of maximum degree contraction problem, Moderately exponential time algorithms for the maximum bounded-degree-1 set problem, Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes, An improved approximation for maximum \(k\)-dependent set on bipartite graphs, Continuous cubic formulations for cluster detection problems in networks, On structural parameterizations of the bounded-degree vertex deletion problem, On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Efficient bounds for the stable set, vertex cover and set packing problems
- Unit disk graphs
- Unit disk graph recognition is NP-hard
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- Defective coloring revisited
- Improper Colourings of Unit Disk Graphs
- Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
- A graph‐theoretic generalization of the clique concept
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Simple heuristics for unit disk graphs
- Independence and Coloring Problems on Intersection Graphs of Disks
- An inequality for the chromatic number of a graph
- Approximation and Online Algorithms
