On-line maximum independent set in chordal graphs

• Autorzy: Christodoulou G. , Zissimopoulos V.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

maximum independent set; chordal graph

PL

graf

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2005
• Tom: Vol. 30, No. 4
• Strony: 283--296
• Opis fizyczny: Bibliogr. 34 poz.

Twórcy

autor

Christodoulou G.

• Department of Informatics and Telecommmunications, University of Athens, 157 84 Athens, Greece

autor

Zissimopoulos V.

• Department of Informatics and Telecommmunications, University of Athens, 157 84 Athens, Greece

Bibliografia

• [1] R. S. Anand and T. Erlebach. On-line algorithms for edge-disjoint paths in trees of rings. In LATIN 2002: Theoretical Informatics, 5th Latin American Symposium, Саncun Mexico, April 3-6, 2002, Proceedings, volume 2286 of Lecture Notes in Computer Science, pages 584-597. Springer, 2002.
• [2] J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts. On-line load balancing with applications to machine scheduling and virtual circuit routing. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 623-631, 1993.
• [3] B. Awerbuch, Y. Azar, and S. Plotkin. Throughput-competitive on-line routing. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science FOCS'93, pages 32-40, 1993.
• [4] В. Awerbuch, Y. Bartal, А. Fiat, and A. Rosen. Competitive non-preemptive call control. In SODA: ACM-SIAM Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms), 1994.
• [5] B. Awerbuch, R. Gawlick, T. Leighton, and Y. Rabani. On-line admission control and circuit routing for high performance computing and communication. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science FOCS'94, pages 412-423, 1994.
• [6] Y. Bartal, A. Fiat, and S. Leonardi. Lower bounds for on-line graph problems with application to on-line circuit and optical routing. In STOC, pages 531-540, 1996.
• [7] P. A. Bernstein and N. Goodman. Power of natural semijoins. SIAM J. Computing, 10:751-771, 1981.
• [8] A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
• [9] M. Demange, X. Paradon, and V. T. Paschos. On-line maximum-order induces hereditary subgraph problems. In SOFSEM 2000: Theory and Practice of Informatics, 27th Conference on Current Trends in Theory and Practice of Informatics, Milovy, Czech Republic, November 25 -December 2, 2000, Proceedings, volume 1963 of Lecture Notes in Computer Science, pages 327-335. Springer, 2000.
• [10] X. Deng, Y. Zhou, G. Li, and W. Zang. A 2-approximation algorithm for path coloring on trees of rings. In Proceedings of the 11th Annual International Symposium on Algorithms and Computation ISAAC 2000, pages 144-155, 2000.
• [11] T. Erlebach. Approximation algorithms and complexity results for path problems in trees of rings. In Sgall et al. [29], pages 351-362.
• [12] T. Erlebach and K. Jansen. Conversion of coloring algorithms into maximum weight independent set algorithms. In ICALP Satellite Workshops, pages 135-146, 2000.
• [13] T. Erlebach and K. Jansen. The complexity of path coloring and call scheduling. Theoretical Computer Science, 255( l-2):33-50, 2001.
• [14] T. Erlebach and K. Jansen. The maximum edge-disjoint paths problem in bidirected trees. SIJDM: SIAM Journal on Discrete Mathematics, 14, 2001.
• [15] T. Erlebach, K. Jansen, C. Kaklamanis, M. Mihail, and P. Persiano. Optimal wavelength routing on directed fiber trees. Theoretical Computer Science, 221(1-2):119-137, 1999.
• [16] J. A. Garay and I. S. Gopal. Call preemption in communication networks. In IEEE INFOCOM '92, The Conference on Computer Communications, Eleventh Annual Joint Conference of the IEEE Computer and Communications Societies, One World through Communications, May 4-8, 1992, Florence, Italy. IEEE, volume 3 of Lecture Notes in Computer Science, pages 1043-1050, 1992.
• [17] M. R. Garey, D.S. Johnson, G. L. Miller, and C. Papadimitriou. The complexity of coloring circular arcs and chords. SIAM J, Algebraic Discrete Methods, l(2):216-227, 1980.
• [18] F. Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Computing, 1(2):180-187, 1972.
• [19] F. Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. Combinatorial Theory, 16:47-56, 1974.
• [20] P. Gilmore and A.J. Hoffman. A characterization of comparability graphs and of interval graphs. Canadian Journal of Mathematics, 15:539-548, 1964.
• [21] M. Halldorsson. Online coloring known graphs. In SODA: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 917-918, 1999.
• [22] M. Halldorsson, K. Iwama, S. Miyazaki, and S. Taketomi. Online independent sets. In Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26-28, 2000, Proceedings, volume 1858 of Lecture Notes in Computer Science, pages 202-209. Springer, 2000.
• [23] M. Halldorsson and M. Szegedy. Lower bounds for on-line graph coloring. In SODA: Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, pages 211-216, 1992.
• [24] R. Kumar, R. Panigrahy, A. Russel, and R. Sundaram. A note on optical routing on trees. Information Processing Letters, 62:295-300, 1997.
• [25] Y. Liang, S. К. Dhall, and S. Lakshmivaraban. Parallel approximate algorithms for node ranking of trees. In Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing, pages 26-31, 1990.
• [26] M. Mihail, C. Kaklamanis, and S. Rao. Efficient access to optical bandwidth - wavelength routing on directed fiber trees, rings, and trees of rings. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science FOCS'95, pages 548-557, 1995.
• [27] P. Raghavan and E. Upfal. Efficient routing in all-optical networks. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing STOC'94 pages 134-143, 1994.
• [28] D. J. Rose, R. E. Tarjan, and G. S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing, 5(2):266-283, 1976.
• [29] J. Sgall, A. Pultr, and P. Kolman, editors. Mathematical Foundations of Computer Science 2001, 26th International Symposium, MFCS 2001 Marianske Lazne, Czech Republic, August 27-31, 2001, Proceedings, volume 2136 of Lecture Notes in Computer Science. Springer, 2001.
• [30] D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of ACM, 28(2):202-208, 1985.
• [31] J. Spinrad. Efficient Graph Representations. American Mathematical Society, 2003.
• [32] R. E. Tarjan and M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13(3):566-579, 1984.
• [33] J. V. Leeuwen. Graph Algorithms, volume A of Handbook of Theoretical Computer Science. The MIT Press, 1990.
• [34] G. Wilfong and P. Winkler. Ring routing and wavelength translation. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms SODA'98, pages 333-341, 1998.