Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: chordal graph

Sortuj według:

Ogranicz wyniki do:

On-line maximum independent set in chordal graphs

Christodoulou G., Zissimopoulos V.

Foundations of Computing and Decision Sciences

2005

Vol. 30, No. 4

283-296

In this paper we deal with the on-line maximum independent set and we propose a probabilistic O(logn)-competitive algorithm for chordal and interval graphs, proving that the same ratio is a lower bound of the problem. The relation of the on-line maximum independent set with the on-line admission control, allows us to obtain as particular case, an O(logn)-competitive algorithm for the on-line admission control in trees and lines. In addition to that, we propose a competitive algorithm for the on-line call admission of subtrees in trees.