Polynomial time recognition of unit circular-arc graphs

We present an efficient algorithm for recognizing unit circular-arc (UCA) graphs, based on a characterization theorem for UCA graphs proved by Tucker in the seventies. Given a proper circular-arc (PCA) graph G, the algorithm starts from a PCA model for G, removes all its circle-covering pairs of arc...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Durán, G., Gravano, A., McConnell, R.M., Spinrad, J., Tucker, A.
Formato: JOUR
Materias:
Circular-arc graphs
Graph algorithms
Polynomial recognition
Proper circular-arc graphs
Unit circular-arc graphs
Approximation theory
Graph theory
Mathematical models
Polynomials
Principal component analysis
Theorem proving
Algorithms
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_01966774_v58_n1_p67_Duran
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

Ejemplares similares

Ejemplares similares