Fully Dynamic Recognition of Proper Circular-Arc Graphs

Mostrar todas las versiones(2)

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(log n) time, where n is the number of vertices of the gr...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Soulignac, Francisco Juan
Publicado: 2013
Materias:
Co-connectivity
Dynamic recognition
Minimal forbidden induced subgraphs
Proper circular-arc graphs
Round graphs
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v_n_p1_Soulignac
http://hdl.handle.net/20.500.12110/paper_01784617_v_n_p1_Soulignac
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_01784617_v_n_p1_Soulignac
record_format dspace
spelling paper:paper_01784617_v_n_p1_Soulignac2023-06-08T15:19:18Z 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 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(log n) time, where n is the number of vertices of the graph, while vertex operations cost O(log n+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(log n) 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. 2013 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v_n_p1_Soulignac http://hdl.handle.net/20.500.12110/paper_01784617_v_n_p1_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
spellingShingle Co-connectivity
Dynamic recognition
Minimal forbidden induced subgraphs
Proper circular-arc graphs
Round graphs
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
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(log n) time, where n is the number of vertices of the graph, while vertex operations cost O(log n+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(log n) 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 2013
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v_n_p1_Soulignac
http://hdl.handle.net/20.500.12110/paper_01784617_v_n_p1_Soulignac
work_keys_str_mv AT soulignacfranciscojuan fullydynamicrecognitionofpropercirculararcgraphs
_version_ 1768543842059943936

Ejemplares similares