A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
| Autor: | Soulignac, Francisco J. |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We present a dynamic algorithm for the recognition of proper circular-arc (PCA) graphs, that supports the insertion and removal of vertices (together with its incident edges). The main feature of the algorithm is that it outputs a minimally non-PCA induced subgraph when the insertion of a vertex fails. Each operation cost $O(\log n + d)$ time, where $n$ is the number vertices and $d$ is the degree of the modified vertex. When removals are disallowed, each insertion is processed in $O(d)$ time. The algorithm also provides two constant-time operations to query if the dynamic graph is proper Helly (PHCA) or proper interval (PIG). When the dynamic graph is not PHCA (resp. PIG), a minimally non-PHCA (resp. non-PIG) induced subgraph is obtained. Comment: 44 pages, 8 figures, appendix with 11 pages and many figures |
| Databáze: | arXiv |
| Externí odkaz: |
|