Comments on "$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs"
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915035205337088 |
|---|---|
| author | Krawczyk, Tomasz |
| author_facet | Krawczyk, Tomasz |
| contents | In the work [$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs, SIAM J. Comput. 24(3), 411--439, (1995)], Wen-Lian Hsu claims three results concerning the class of circular-arc graphs: - the design of so-called \emph{decomposition trees} that represent the structure of all normalized intersection models of circular-arc graphs, - an $\mathcal{O}(m\cdot n)$ recognition algorithm for circular-arc graphs, - an $\mathcal{O}(m\cdot n)$ isomorphism algorithm for circular-arc graphs. In [Discrete Math. Theor. Comput. Sci., 15(1), 157--182, 2013] Curtis, Lin, McConnell, Nussbaum, Soulignac, Spinrad, and Szwarcfiter showed that Hsu's isomorphism algorithm is incorrect. In this note, we show that the other two results -- namely, the construction of decomposition trees and the recognition algorithm -- are also flawed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_13708 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Comments on "$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs" Krawczyk, Tomasz Data Structures and Algorithms Combinatorics E.1; F.2 In the work [$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs, SIAM J. Comput. 24(3), 411--439, (1995)], Wen-Lian Hsu claims three results concerning the class of circular-arc graphs: - the design of so-called \emph{decomposition trees} that represent the structure of all normalized intersection models of circular-arc graphs, - an $\mathcal{O}(m\cdot n)$ recognition algorithm for circular-arc graphs, - an $\mathcal{O}(m\cdot n)$ isomorphism algorithm for circular-arc graphs. In [Discrete Math. Theor. Comput. Sci., 15(1), 157--182, 2013] Curtis, Lin, McConnell, Nussbaum, Soulignac, Spinrad, and Szwarcfiter showed that Hsu's isomorphism algorithm is incorrect. In this note, we show that the other two results -- namely, the construction of decomposition trees and the recognition algorithm -- are also flawed. |
| title | Comments on "$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs" |
| topic | Data Structures and Algorithms Combinatorics E.1; F.2 |
| url | https://arxiv.org/abs/2411.13708 |