Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs

DOI10.1016/j.dam.2006.04.036zbMath1110.05075OpenAlexW2049061549MaRDI QIDQ867854

Christos Kaklamanis, Ioannis Caragiannis, Aleksei V. Fishkin, Evi Papaioannou

Publication date: 19 February 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.036

zbMATH Keywords

competitive analysis

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Scheduling to maximize participation ⋮ Independent sets in graphs ⋮ Online algorithms with advice: the tape model ⋮ Scheduling to Maximize Participation ⋮ Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs

Cites Work

• Unnamed Item
• 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
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Simple heuristics for unit disk graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Independence and Coloring Problems on Intersection Graphs of Disks
• Graph-Theoretic Concepts in Computer Science
• Representing graphs by disks and balls (a survey of recognition-complexity results)
• On-line competitive algorithms for call admission in optical networks

This page was built for publication: Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs