Unit circular-arc graph representations and feasible circulations

In a recent paper, Duran et al. [J. Algorithms, 58 (2006), pp. 67-78] described an algorithm of complexity O(n2) for recognizing whether a graph G with n vertices and m edges is a unit circular-arc (UCA) graph. Furthermore, the following open questions were posed in the above paper: (i) Is it possib...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Lin, Min Chih
Publicado:	2008
Materias:	Algorithm Circular-arc graph Circular-arc model Circulations Networks Proper circular-arc graph Unit circular-arc graph Algorithms Cavity resonators Graph theory Paper Polynomial approximation Mathematical models
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_08954801_v22_n1_p409_Lin http://hdl.handle.net/20.500.12110/paper_08954801_v22_n1_p409_Lin
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_08954801_v22_n1_p409_Lin
record_format	dspace
spelling	paper:paper_08954801_v22_n1_p409_Lin2023-06-08T15:48:03Z Unit circular-arc graph representations and feasible circulations Lin, Min Chih Algorithm Circular-arc graph Circular-arc model Circulations Networks Proper circular-arc graph Unit circular-arc graph Algorithms Cavity resonators Graph theory Paper Polynomial approximation Circular-arc graph Circular-arc model Circulations Networks Proper circular-arc graph Unit circular-arc graph Mathematical models In a recent paper, Duran et al. [J. Algorithms, 58 (2006), pp. 67-78] described an algorithm of complexity O(n2) for recognizing whether a graph G with n vertices and m edges 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 UCA 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, based on network circulations. The characterization leads to a different recognition algorithm and to answering these questions in the affirmative. We construct a UCA model whose extremes of the arcs correspond to integers of size O(n). The proposed algorithms, for recognizing UCA graphs and constructing UCA models, have complexities O(n + m). Furthermore, the complexities reduce to O(n), if a proper circular-arc (PCA) model of G is already given as the input, provided the extremes of the arcs are ordered. We remark that a PCA model of G can be constructed in O(n + m) time, using the algorithm by Deng, Hell, and Huang [SIAM J. Comput., 25 (1996), pp. 390-403]. Finally, we also describe a linear time algorithm for finding feasible circulations in networks with nonnegative lower capacities and unbounded upper capacities. Such an algorithm is employed in the model construction for UCA graphs. © 2008 Society for Industrial and Applied Mathematics. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2008 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_08954801_v22_n1_p409_Lin http://hdl.handle.net/20.500.12110/paper_08954801_v22_n1_p409_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	Algorithm Circular-arc graph Circular-arc model Circulations Networks Proper circular-arc graph Unit circular-arc graph Algorithms Cavity resonators Graph theory Paper Polynomial approximation Circular-arc graph Circular-arc model Circulations Networks Proper circular-arc graph Unit circular-arc graph Mathematical models
spellingShingle	Algorithm Circular-arc graph Circular-arc model Circulations Networks Proper circular-arc graph Unit circular-arc graph Algorithms Cavity resonators Graph theory Paper Polynomial approximation Circular-arc graph Circular-arc model Circulations Networks Proper circular-arc graph Unit circular-arc graph Mathematical models Lin, Min Chih Unit circular-arc graph representations and feasible circulations
topic_facet	Algorithm Circular-arc graph Circular-arc model Circulations Networks Proper circular-arc graph Unit circular-arc graph Algorithms Cavity resonators Graph theory Paper Polynomial approximation Circular-arc graph Circular-arc model Circulations Networks Proper circular-arc graph Unit circular-arc graph Mathematical models
description	In a recent paper, Duran et al. [J. Algorithms, 58 (2006), pp. 67-78] described an algorithm of complexity O(n2) for recognizing whether a graph G with n vertices and m edges 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 UCA 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, based on network circulations. The characterization leads to a different recognition algorithm and to answering these questions in the affirmative. We construct a UCA model whose extremes of the arcs correspond to integers of size O(n). The proposed algorithms, for recognizing UCA graphs and constructing UCA models, have complexities O(n + m). Furthermore, the complexities reduce to O(n), if a proper circular-arc (PCA) model of G is already given as the input, provided the extremes of the arcs are ordered. We remark that a PCA model of G can be constructed in O(n + m) time, using the algorithm by Deng, Hell, and Huang [SIAM J. Comput., 25 (1996), pp. 390-403]. Finally, we also describe a linear time algorithm for finding feasible circulations in networks with nonnegative lower capacities and unbounded upper capacities. Such an algorithm is employed in the model construction for UCA graphs. © 2008 Society for Industrial and Applied Mathematics.
author	Lin, Min Chih
author_facet	Lin, Min Chih
author_sort	Lin, Min Chih
title	Unit circular-arc graph representations and feasible circulations
title_short	Unit circular-arc graph representations and feasible circulations
title_full	Unit circular-arc graph representations and feasible circulations
title_fullStr	Unit circular-arc graph representations and feasible circulations
title_full_unstemmed	Unit circular-arc graph representations and feasible circulations
title_sort	unit circular-arc graph representations and feasible circulations
publishDate	2008
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_08954801_v22_n1_p409_Lin http://hdl.handle.net/20.500.12110/paper_08954801_v22_n1_p409_Lin
work_keys_str_mv	AT linminchih unitcirculararcgraphrepresentationsandfeasiblecirculations
_version_	1768546121084305408

Unit circular-arc graph representations and feasible circulations

Ejemplares similares