On the power of standard DFS and BFS
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910188458475520 |
|---|---|
| author | Bui-Xuan, Binh-Minh Habib, Michel de Montgolfier, Fabien Torfs, Renaud |
| author_facet | Bui-Xuan, Binh-Minh Habib, Michel de Montgolfier, Fabien Torfs, Renaud |
| contents | It is well-known since the seventies of last century that Depth First Search (DFS) can be used to compute strongly connected components [RE. Tarjan. SIAM Journal on Computing, 1972] and Breadth First Search (BFS) can be used to compute distance in graphs [GY. Handler. Transportation Science, 1973]. We furthermore demonstrate that these standard graph searches are powerful enough to recognize and certify several well-structured graph classes. Specifically, we provide a single DFS approach for recognizing and certifying trivially perfect graphs that is significantly simpler than previous methods using [FPM. Chu. Information Processing Letters, 2008]. We further show that a single BFS can recognize split graphs and bipartite chain graphs, and we improve upon the triple LexBFS algorithm for proper interval graphs [DG. Corneil. Discrete Applied Mathematics, 2004] by proposing a two consecutive BFS recognition scheme. These results are underpinned by characterizations using vertex orderings that avoid specific patterns [L. Feuilloley, M. Habib. SIAM Journal on Discrete Mathematics, 2021]. Finally, we provide a structural study of connected proper interval graphs, proving that their characterizations via special orderings are unique up to reversal and the permutation of true twins. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_02387 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the power of standard DFS and BFS Bui-Xuan, Binh-Minh Habib, Michel de Montgolfier, Fabien Torfs, Renaud Data Structures and Algorithms It is well-known since the seventies of last century that Depth First Search (DFS) can be used to compute strongly connected components [RE. Tarjan. SIAM Journal on Computing, 1972] and Breadth First Search (BFS) can be used to compute distance in graphs [GY. Handler. Transportation Science, 1973]. We furthermore demonstrate that these standard graph searches are powerful enough to recognize and certify several well-structured graph classes. Specifically, we provide a single DFS approach for recognizing and certifying trivially perfect graphs that is significantly simpler than previous methods using [FPM. Chu. Information Processing Letters, 2008]. We further show that a single BFS can recognize split graphs and bipartite chain graphs, and we improve upon the triple LexBFS algorithm for proper interval graphs [DG. Corneil. Discrete Applied Mathematics, 2004] by proposing a two consecutive BFS recognition scheme. These results are underpinned by characterizations using vertex orderings that avoid specific patterns [L. Feuilloley, M. Habib. SIAM Journal on Discrete Mathematics, 2021]. Finally, we provide a structural study of connected proper interval graphs, proving that their characterizations via special orderings are unique up to reversal and the permutation of true twins. |
| title | On the power of standard DFS and BFS |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2605.02387 |