Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
type: Item
instance of: scholarly article
title: Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
zbMATH Open document ID: 1110.05075
author: I. Caragiannis
author: Aleksei V. Fishkin
author: C. Kaklamanis
author: Evi Papaioannou
published in: Discrete Applied Mathematics
publication date: 2007-02-19T00:00:00Z
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5128017
zbMATH Keywords: competitive analysis
MaRDI profile type: Publication
full work available at URL: j.dam.2006.04.036
OpenAlex ID: W2049061549
cites work: On-line competitive algorithms for call admission in optical networks
cites work: Q3128890
cites work: Q4223058
cites work: Polynomial-time approximation schemes for packing and piercing fat objects
cites work: Unit disk graphs
cites work: Independence and Coloring Problems on Intersection Graphs of Disks
cites work: Polynomial-time approximation schemes for geometric graphs
cites work: Q4886045
cites work: Representing graphs by disks and balls (a survey of recognition-complexity results)
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: Q3128889
cites work: Simple heuristics for unit disk graphs
cites work: Q4504025
cites work: Graph-Theoretic Concepts in Computer Science
DOI: 10.1016/J.DAM.2006.04.036
Recommended article: Approximation algorithms for maximum independent set of a unit disk graph
Recommended article: Faster approximation for maximum independent set on unit disk graph
Recommended article: Efficient independent set approximation in unit disk graphs
Recommended article: Approximation algorithms for maximum independent set of pseudo-disks
Recommended article: Structural Information and Communication Complexity
Recommended article: Q4504025
Recommended article: Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs
Recommended article: Computing independent sets in graphs with large girth
Recommended article: Q2766819
description: scientific article; zbMATH DE number 5128017