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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Soulignac, Francisco Juan
Publicado: 2015
Materias:
Co-connectivity
Dynamic recognition
Minimal forbidden induced subgraphs
Proper circular-arc graphs
Round graphs
Algorithms
Graphic methods
Connectivity algorithms
Decremental algorithms
Forbidden induced subgraphs
Fully dynamic algorithms
Induced subgraphs
Graph theory
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:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

Ejemplares similares

Ejemplares similares