Linear time algorithms on circular-arc graphs. (English) Zbl 0748.68044
Summary: Circular-arc graphs are rich in combinatorial structures. Various characterization and optimization problems on circular-arc graphs have been studied. We present an extremely simple \(O(n)\) algorithm which simultaneously solves the following three problems (the unweighted versions) on circular-arc graphs: the maximum independent set, the minimum clique cover, and the minimum dominating set problems; whereas the best previous bounds for the latter two problems were \(O(n^ 2)\) and \(O(n^ 3)\), respectively. Our approach takes advantage of the underlying structure of circular-arc graphs that is amenable to greedy algorithms.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68R05 | Combinatorics in computer science |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Bonuccelli, M. A., Dominating sets and domatic number of circular-arc graphs, Discrete Appl. Math., 12, 203-213 (1985) · Zbl 0579.05051 |
| [2] | Golumbic, M. C.; Hammer, P., Stability in circular-arc graphs, J. Algorithms, 9, 314-320 (1988) · Zbl 0651.68083 |
| [3] | Gupta, U. I.; Lee, D. T.; Leung, J. Y.-T., Efficient algorithms for interval graphs and circular-arc graphs, Networks, 12, 459-467 (1982) · Zbl 0493.68066 |
| [4] | Hsu, W. L.; Tsai, K. H., Linear time algorithms on circular-arc graphs, Proc. 26th Ann. Allerton Conf., 842-851 (1988) |
| [5] | Masuda, S.; Nakajima, K., An optimal algorithm for finding a maximum independent set of a circular-arc graph, SIAM J. Comput., 17, 41-52 (1988) · Zbl 0646.68084 |
| [6] | Rhee, C., Parallel algorithms for special graphs, (Ph.D. Dissertation (1990), University of Oklahoma: University of Oklahoma Norman, OK) |
| [7] | Yu, M. S.; Chen, C. L.; Lee, R. C.T., Optimal algorithms for the minimum dominating set problem on circular-arc graphs, Proc. First Ann. IEEE Symp. on Parallel and Distributed Computing, 3-10 (1989) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
