Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes

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

zbMATH Keywords

graph coloringindependent set\(k\)-dependent setdefective coloring\(t\)-improper coloringco-\(k\)-plex

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

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