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...
Guardado en:
| Autor principal: | |
|---|---|
| Publicado: |
2008
|
| Materias: | |
| 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: |
| Sumario: | 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. |
|---|