Fully Dynamic Recognition of Proper Circular-Arc Graphs
We present a fully dynamic algorithm for the recognition of proper circular-arc (PCA) graphs. The allowed operations on the graph involve the insertion and removal of vertices (together with its incident edges) or edges. Edge operations cost O(logn) time, where n is the number of vertices of the gra...
Guardado en:
Autor principal: | |
---|---|
Publicado: |
2015
|
Materias: | |
Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v71_n4_p904_Soulignac http://hdl.handle.net/20.500.12110/paper_01784617_v71_n4_p904_Soulignac |
Aporte de: |
id |
paper:paper_01784617_v71_n4_p904_Soulignac |
---|---|
record_format |
dspace |
spelling |
paper:paper_01784617_v71_n4_p904_Soulignac2023-06-08T15:19:17Z Fully Dynamic Recognition of Proper Circular-Arc Graphs Soulignac, Francisco Juan Co-connectivity Dynamic recognition Minimal forbidden induced subgraphs Proper circular-arc graphs Round graphs Algorithms Graphic methods Connectivity algorithms Decremental algorithms Dynamic recognition Forbidden induced subgraphs Fully dynamic algorithms Induced subgraphs Proper circular-arc graphs Round graphs Graph theory We present a fully dynamic algorithm for the recognition of proper circular-arc (PCA) graphs. The allowed operations on the graph involve the insertion and removal of vertices (together with its incident edges) or edges. Edge operations cost O(logn) time, where n is the number of vertices of the graph, while vertex operations cost O(logn+d) time, where d is the degree of the modified vertex. We also show incremental and decremental algorithms that work in O(1) time per inserted or removed edge. As part of our algorithm, fully dynamic connectivity and co-connectivity algorithms that work in O(logn) time per operation are obtained. Also, an O(Δ) time algorithm for determining if a PCA representation corresponds to a co-bipartite graph is provided, where Δ is the maximum among the degrees of the vertices. When the graph is co-bipartite, a co-bipartition of each of its co-components is obtained within the same amount of time. As an application, we show how to find a minimal forbidden induced subgraph of a static graph in O(n+m) time. © 2013, Springer Science+Business Media New York. Fil:Soulignac, F.J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2015 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v71_n4_p904_Soulignac http://hdl.handle.net/20.500.12110/paper_01784617_v71_n4_p904_Soulignac |
institution |
Universidad de Buenos Aires |
institution_str |
I-28 |
repository_str |
R-134 |
collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
topic |
Co-connectivity Dynamic recognition Minimal forbidden induced subgraphs Proper circular-arc graphs Round graphs Algorithms Graphic methods Connectivity algorithms Decremental algorithms Dynamic recognition Forbidden induced subgraphs Fully dynamic algorithms Induced subgraphs Proper circular-arc graphs Round graphs Graph theory |
spellingShingle |
Co-connectivity Dynamic recognition Minimal forbidden induced subgraphs Proper circular-arc graphs Round graphs Algorithms Graphic methods Connectivity algorithms Decremental algorithms Dynamic recognition Forbidden induced subgraphs Fully dynamic algorithms Induced subgraphs Proper circular-arc graphs Round graphs Graph theory Soulignac, Francisco Juan Fully Dynamic Recognition of Proper Circular-Arc Graphs |
topic_facet |
Co-connectivity Dynamic recognition Minimal forbidden induced subgraphs Proper circular-arc graphs Round graphs Algorithms Graphic methods Connectivity algorithms Decremental algorithms Dynamic recognition Forbidden induced subgraphs Fully dynamic algorithms Induced subgraphs Proper circular-arc graphs Round graphs Graph theory |
description |
We present a fully dynamic algorithm for the recognition of proper circular-arc (PCA) graphs. The allowed operations on the graph involve the insertion and removal of vertices (together with its incident edges) or edges. Edge operations cost O(logn) time, where n is the number of vertices of the graph, while vertex operations cost O(logn+d) time, where d is the degree of the modified vertex. We also show incremental and decremental algorithms that work in O(1) time per inserted or removed edge. As part of our algorithm, fully dynamic connectivity and co-connectivity algorithms that work in O(logn) time per operation are obtained. Also, an O(Δ) time algorithm for determining if a PCA representation corresponds to a co-bipartite graph is provided, where Δ is the maximum among the degrees of the vertices. When the graph is co-bipartite, a co-bipartition of each of its co-components is obtained within the same amount of time. As an application, we show how to find a minimal forbidden induced subgraph of a static graph in O(n+m) time. © 2013, Springer Science+Business Media New York. |
author |
Soulignac, Francisco Juan |
author_facet |
Soulignac, Francisco Juan |
author_sort |
Soulignac, Francisco Juan |
title |
Fully Dynamic Recognition of Proper Circular-Arc Graphs |
title_short |
Fully Dynamic Recognition of Proper Circular-Arc Graphs |
title_full |
Fully Dynamic Recognition of Proper Circular-Arc Graphs |
title_fullStr |
Fully Dynamic Recognition of Proper Circular-Arc Graphs |
title_full_unstemmed |
Fully Dynamic Recognition of Proper Circular-Arc Graphs |
title_sort |
fully dynamic recognition of proper circular-arc graphs |
publishDate |
2015 |
url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v71_n4_p904_Soulignac http://hdl.handle.net/20.500.12110/paper_01784617_v71_n4_p904_Soulignac |
work_keys_str_mv |
AT soulignacfranciscojuan fullydynamicrecognitionofpropercirculararcgraphs |
_version_ |
1768544637724655616 |