Randomized On-line Algorithms and Lower Bounds for Computing Large Independent 
Sets in Disk Graphs

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

doi:10.1016/j.dam.2006.04.036

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

Randomized On-line Algorithms and Lower Bounds for Computing Large Independent Sets in Disk Graphs

MPS-Authors

/persons/resource/persons44429

Fishkin, Aleksei V.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

Caragiannis, I., Fishkin, A. V., Kaklamanis, C., & Papaioannou, E. (2007). Randomized On-line Algorithms and Lower Bounds for Computing Large Independent Sets in Disk Graphs. In J., Kratochvíl, J., Díaz, & J., Fiala (Eds.), 29th Symposium on Mathematical Foundations of Computer Science (pp. 119-136). Amsterdam: Elsevier. doi:10.1016/j.dam.2006.04.036.

引用: https://hdl.handle.net/11858/00-001M-0000-000F-206F-7

要旨

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.