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
Autores principales: Lin, M.C., Szwarcfiter, J.L.
Formato: CONF
Materias:
Algorithms
Graph theory
Polynomials
Time series analysis
Circular-arc models
Integers
Vertices
Mathematical models
Acceso en línea: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 todo:paper_NIS07298_v_n_p309_Lin
record_format dspace
spelling todo:paper_NIS07298_v_n_p309_Lin2023-10-03T16:45:47Z Efficient construction of unit circular-arc models Lin, M.C. Szwarcfiter, J.L. 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. CONF info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, M.C.
Szwarcfiter, J.L.
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.
format CONF
author Lin, M.C.
Szwarcfiter, J.L.
author_facet Lin, M.C.
Szwarcfiter, J.L.
author_sort Lin, M.C.
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
url http://hdl.handle.net/20.500.12110/paper_NIS07298_v_n_p309_Lin
work_keys_str_mv AT linmc efficientconstructionofunitcirculararcmodels
AT szwarcfiterjl efficientconstructionofunitcirculararcmodels
_version_ 1782024996623745024

Ejemplares similares