GREEDY ALGORITHMS FOR OPTIMIZATION PROBLEMS ON UNIT INTERVAL GRAPHS
Main Article Content
Abstract
In this paper, we show a very special property of unit interval graphs and use that property to introduce greedy algorithms for classical optimization problems on them: finding minimum dominating set, maximum independent set and maximum matching. These algorithms are all linear-time concerning the number of vertices of the graph and simple for implementation.
Keywords
unit interval graph, greedy algorithm, optimization problem
Article Details
References
Chang, M. (1998). Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM Journal of Computing, 27(6), 1671-1694.
Heggernes, P., Lokshtanov, D., Mihai, R., & Papadopoulos, C. (2008). Cutwidth of split graphs, threshold graphs, and proper interval graphs. Proceedings of WG 2008, Lecture Notes in Computer Science, 5344, 218-229.
Hsu, W., & Tsai, K. H. (1991). Linear time algorithms on circular-arc graphs.
Information Processing Letters, 40(3), 123-129.
Van Leeuwen, E. J., (2005). Approximation Algorithms for Unit Disk Graphs. In: Kratsch D. (eds) Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, 3787, 351-361.
Yuan, J., & Zhou, S., (1995). Optimal labelling of unit interval graphs. Applied Mathematics-a Journal of Chinese Universities Series B, 10, 337-344.
Heggernes, P., Lokshtanov, D., Mihai, R., & Papadopoulos, C. (2008). Cutwidth of split graphs, threshold graphs, and proper interval graphs. Proceedings of WG 2008, Lecture Notes in Computer Science, 5344, 218-229.
Hsu, W., & Tsai, K. H. (1991). Linear time algorithms on circular-arc graphs.
Information Processing Letters, 40(3), 123-129.
Van Leeuwen, E. J., (2005). Approximation Algorithms for Unit Disk Graphs. In: Kratsch D. (eds) Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, 3787, 351-361.
Yuan, J., & Zhou, S., (1995). Optimal labelling of unit interval graphs. Applied Mathematics-a Journal of Chinese Universities Series B, 10, 337-344.