Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs |
| |
Authors: | Haim Kaplan Yahav Nussbaum |
| |
Affiliation: | aThe Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel |
| |
Abstract: | We give two new linear-time algorithms, one for recognizing proper circular-arc graphs and the other for recognizing unit circular-arc graphs. Both algorithms provide either a model for the input graph, or a certificate that proves that such a model does not exist and can be authenticated in O(n) time. No other previous algorithm for each of these two graph classes provides a certificate for its result. |
| |
Keywords: | Proper circular-arc Unit circular-arc Certifying algorithm Graph recognition |
本文献已被 ScienceDirect 等数据库收录! |