Unit circular-arc graph representations and feasible circulations. (English) Zbl 1232.05145
Summary: G. Durán et al. [J. Algorithms 58, No. 1, 67–78 (2006; Zbl 1093.68071)] described an algorithm of complexity \(O(n^2)\) 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:
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.
- (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?
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.
MSC:
05C62 | Graph representations (geometric and intersection representations, etc.) |
05C85 | Graph algorithms (graph-theoretic aspects) |
05C05 | Trees |
68R10 | Graph theory (including graph drawing) in computer science |