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
id todo:paper_01966774_v58_n1_p67_Duran
record_format dspace
spelling todo:paper_01966774_v58_n1_p67_Duran2023-10-03T15:09:48Z Polynomial time recognition of unit circular-arc graphs Durán, G. Gravano, A. McConnell, R.M. Spinrad, J. Tucker, A. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, G.
Gravano, A.
McConnell, R.M.
Spinrad, J.
Tucker, A.
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.
format JOUR
author Durán, G.
Gravano, A.
McConnell, R.M.
Spinrad, J.
Tucker, A.
author_facet Durán, G.
Gravano, A.
McConnell, R.M.
Spinrad, J.
Tucker, A.
author_sort Durán, G.
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
url http://hdl.handle.net/20.500.12110/paper_01966774_v58_n1_p67_Duran
work_keys_str_mv AT durang polynomialtimerecognitionofunitcirculararcgraphs
AT gravanoa polynomialtimerecognitionofunitcirculararcgraphs
AT mcconnellrm polynomialtimerecognitionofunitcirculararcgraphs
AT spinradj polynomialtimerecognitionofunitcirculararcgraphs
AT tuckera polynomialtimerecognitionofunitcirculararcgraphs
_version_ 1782030565333008384

Ejemplares similares