On-line maximum independent set in chordal graphs
George C. Christodoulou, Vassilios Zissimopoulos · 2005
Abstract. In this paper we deal with the on-line maximum independent set and we propose a probabilistic O(log n)-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(log n)-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. 1