Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
type: Item
instance of: scholarly article
title: Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
zbMATH Open document ID: 1202.90257
author: B. Balasundaram
author: Shyam S. Chandramouli
author: Svyatoslav Trukhanov
published in: Optimization Letters
publication date: 2010-10-04T00:00:00Z
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 5795203
zbMATH Keywords: independent set
zbMATH Keywords: graph coloring
zbMATH Keywords: co-\(k\)-plex
zbMATH Keywords: \(k\)-dependent set
zbMATH Keywords: defective coloring
zbMATH Keywords: \(t\)-improper coloring
MaRDI profile type: Publication
full work available at URL: s11590-009-0146-5
OpenAlex ID: W2090216307
cites work: Q3758854
cites work: Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
cites work: Unit disk graph recognition is NP-hard
cites work: Q5708492
cites work: Unit disk graphs
cites work: Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
cites work: Defective coloring revisited
cites work: Q4268437
cites work: Independence and Coloring Problems on Intersection Graphs of Disks
cites work: Approximation and Online Algorithms
cites work: Q4198056
cites work: Q3744180
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Improper Colourings of Unit Disk Graphs
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
cites work: Simple heuristics for unit disk graphs
cites work: A graph‐theoretic generalization of the clique concept
cites work: An inequality for the chromatic number of a graph
DOI: 10.1007/S11590-009-0146-5
description: scientific article; zbMATH DE number 5795203