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
Autores principales:	Lin, M.C., Szwarcfiter, J.L.
Formato:	JOUR
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:	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	todo:paper_08954801_v22_n1_p409_Lin
record_format	dspace
spelling	todo:paper_08954801_v22_n1_p409_Lin2023-10-03T15:42:22Z Unit circular-arc graph representations and feasible circulations Lin, M.C. Szwarcfiter, J.L. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, M.C. Szwarcfiter, J.L. 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.
format	JOUR
author	Lin, M.C. Szwarcfiter, J.L.
author_facet	Lin, M.C. Szwarcfiter, J.L.
author_sort	Lin, M.C.
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
url	http://hdl.handle.net/20.500.12110/paper_08954801_v22_n1_p409_Lin
work_keys_str_mv	AT linmc unitcirculararcgraphrepresentationsandfeasiblecirculations AT szwarcfiterjl unitcirculararcgraphrepresentationsandfeasiblecirculations
_version_	1807321992291942400

Unit circular-arc graph representations and feasible circulations

Ejemplares similares