Efficient construction of unit circular-arc models

In a recent paper, Durán, Gravano, McConnell, Spinrad and Tucker described an algorithm of complexity O(n2) for recognizing whether a graph G with n vertices is a unit circular-arc (UCA) graph. Furthermore the following open questions were posed in the above paper: (i) Is it possible to construct a...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Lin, Min Chih
Publicado: 2006
Materias:
Algorithms
Graph theory
Polynomials
Time series analysis
Circular-arc models
Integers
Vertices
Mathematical models
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_NIS07298_v_n_p309_Lin
http://hdl.handle.net/20.500.12110/paper_NIS07298_v_n_p309_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_NIS07298_v_n_p309_Lin
record_format dspace
spelling paper:paper_NIS07298_v_n_p309_Lin2023-06-08T16:39:31Z Efficient construction of unit circular-arc models Lin, Min Chih Algorithms Graph theory Polynomials Time series analysis Circular-arc models Integers Vertices Mathematical models In a recent paper, Durán, Gravano, McConnell, Spinrad and Tucker described an algorithm of complexity O(n2) for recognizing whether a graph G with n vertices is a unit circular-arc (UCA) graph. Furthermore the following open questions were posed in the above paper: (i) Is it possible to construct a UCA model for G in polynomial time? (ii) Is it possible to construct a model, whose extremes of the arcs correspond to integers of polynomial size? (iii) If (ii) is true, could such a model be constructed in polynomial time? In the present paper, we describe a characterization of UCA graphs which leads to linear time algorithms for recognizing UCA graphs and constructing UCA models. Furthermore, we construct models whose extreme of the arcs correspond to integers of size O(n). The proposed algorithms provide positive answers to the three above questions. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2006 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_NIS07298_v_n_p309_Lin http://hdl.handle.net/20.500.12110/paper_NIS07298_v_n_p309_Lin
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Algorithms
Graph theory
Polynomials
Time series analysis
Circular-arc models
Integers
Vertices
Mathematical models
spellingShingle Algorithms
Graph theory
Polynomials
Time series analysis
Circular-arc models
Integers
Vertices
Mathematical models
Lin, Min Chih
Efficient construction of unit circular-arc models
topic_facet Algorithms
Graph theory
Polynomials
Time series analysis
Circular-arc models
Integers
Vertices
Mathematical models
description In a recent paper, Durán, Gravano, McConnell, Spinrad and Tucker described an algorithm of complexity O(n2) for recognizing whether a graph G with n vertices is a unit circular-arc (UCA) graph. Furthermore the following open questions were posed in the above paper: (i) Is it possible to construct a UCA model for G in polynomial time? (ii) Is it possible to construct a model, whose extremes of the arcs correspond to integers of polynomial size? (iii) If (ii) is true, could such a model be constructed in polynomial time? In the present paper, we describe a characterization of UCA graphs which leads to linear time algorithms for recognizing UCA graphs and constructing UCA models. Furthermore, we construct models whose extreme of the arcs correspond to integers of size O(n). The proposed algorithms provide positive answers to the three above questions.
author Lin, Min Chih
author_facet Lin, Min Chih
author_sort Lin, Min Chih
title Efficient construction of unit circular-arc models
title_short Efficient construction of unit circular-arc models
title_full Efficient construction of unit circular-arc models
title_fullStr Efficient construction of unit circular-arc models
title_full_unstemmed Efficient construction of unit circular-arc models
title_sort efficient construction of unit circular-arc models
publishDate 2006
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_NIS07298_v_n_p309_Lin
http://hdl.handle.net/20.500.12110/paper_NIS07298_v_n_p309_Lin
work_keys_str_mv AT linminchih efficientconstructionofunitcirculararcmodels
_version_ 1769175819123425280

Ejemplares similares