Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs |
| |
| Authors: | Ioannis Caragiannis Evi Papaioannou |
| |
| Institution: | a Research Academic Computer Technology Institute and Department of Computer Engineering and Informatics, University of Patras, 26500 Rio, Greece
b Max-Planck-Institut für Informatik, Im Stadtwald, Geb. 46.1, 66123 Saarbrücken, Germany |
| |
| Abstract: | We study the on-line version of the maximum independent set problem, for the case of disk graphs which are graphs resulting from intersections of disks on the plane. In particular, we investigate whether randomization can be used to break known lower bounds for deterministic on-line independent set algorithms and present new upper and lower bounds. |
| |
| Keywords: | On-line algorithms Competitive analysis Maximum independent set Disk graphs |
| 本文献已被 ScienceDirect 等数据库收录！ |
