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

Ejemplares similares

Ejemplares similares