Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
From MaRDI portal
Publication:1958629
DOI10.1007/s11590-009-0146-5zbMath1202.90257OpenAlexW2090216307MaRDI 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 coloringindependent set\(k\)-dependent setdefective coloring\(t\)-improper coloringco-\(k\)-plex
Related Items
On the parameterized complexity of maximum degree contraction problem, Moderately exponential time algorithms for the maximum bounded-degree-1 set problem, Finding maximum subgraphs with relatively large vertex connectivity, On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem, Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes, Maximum weight t-sparse set problem on vector-weighted graphs, Asymptotic bounds for clustering problems in random graphs, On structural parameterizations of the bounded-degree vertex deletion problem, Co-2-plex vertex partitions, On the Parameterized Complexity of Maximum Degree Contraction Problem., An improved approximation for maximum \(k\)-dependent set on bipartite graphs, On bounded-degree vertex deletion parameterized by treewidth, Continuous cubic formulations for cluster detection problems in networks
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