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

Detalles Bibliográficos
Autores principales: Durán, Guillermo A., Gravano, Agustín
Publicado: 2006
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:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01966774_v58_n1_p67_Duran
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
id paper:paper_01966774_v58_n1_p67_Duran
record_format dspace
spelling paper:paper_01966774_v58_n1_p67_Duran2023-06-08T15:20:31Z Polynomial time recognition of unit circular-arc graphs Durán, Guillermo A. Gravano, Agustín 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 Circular-arc graphs Graph algorithms Polynomial recognition Proper circular-arc graphs Unit circular-arc graphs Algorithms 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 arcs and determines whether G is a UCA graph. We also give an O(N) time bound for Tucker's 3/2-approximation algorithm for coloring circular-arc graphs with N vertices, when a circular-arc model is given. © 2004 Elsevier Inc. All rights reserved. Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Gravano, A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2006 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01966774_v58_n1_p67_Duran http://hdl.handle.net/20.500.12110/paper_01966774_v58_n1_p67_Duran
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic 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
Circular-arc graphs
Graph algorithms
Polynomial recognition
Proper circular-arc graphs
Unit circular-arc graphs
Algorithms
spellingShingle 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
Circular-arc graphs
Graph algorithms
Polynomial recognition
Proper circular-arc graphs
Unit circular-arc graphs
Algorithms
Durán, Guillermo A.
Gravano, Agustín
Polynomial time recognition of unit circular-arc graphs
topic_facet 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
Circular-arc graphs
Graph algorithms
Polynomial recognition
Proper circular-arc graphs
Unit circular-arc graphs
Algorithms
description 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 arcs and determines whether G is a UCA graph. We also give an O(N) time bound for Tucker's 3/2-approximation algorithm for coloring circular-arc graphs with N vertices, when a circular-arc model is given. © 2004 Elsevier Inc. All rights reserved.
author Durán, Guillermo A.
Gravano, Agustín
author_facet Durán, Guillermo A.
Gravano, Agustín
author_sort Durán, Guillermo A.
title Polynomial time recognition of unit circular-arc graphs
title_short Polynomial time recognition of unit circular-arc graphs
title_full Polynomial time recognition of unit circular-arc graphs
title_fullStr Polynomial time recognition of unit circular-arc graphs
title_full_unstemmed Polynomial time recognition of unit circular-arc graphs
title_sort polynomial time recognition of unit circular-arc graphs
publishDate 2006
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01966774_v58_n1_p67_Duran
http://hdl.handle.net/20.500.12110/paper_01966774_v58_n1_p67_Duran
work_keys_str_mv AT duranguillermoa polynomialtimerecognitionofunitcirculararcgraphs
AT gravanoagustin polynomialtimerecognitionofunitcirculararcgraphs
_version_ 1768546111958548480

Ejemplares similares