Name
Abstract | ||
|---|---|---|
In a recent paper, Durán et al. [J. Algorithms, 58 (2006), pp. 67-78] 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: (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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/060650805 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
networks,unit circular-arc graph.,circular-arc model,different recognition algorithm,feasible circulations,proposed algorithm,unit circular-arc graph representations,proper circular-arc graph,algorithm,uca graph,uca model,linear time algorithm,present paper,circular-arc graph,pca model,polynomial time,circulations,polynomial size,model construction,graph representation | Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Algorithm complexity,Polynomial,Circular-arc graph,Recognition algorithm,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 1 | 0895-4801 |
Citations | PageRank | References |
10 | 0.66 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Min Chih Lin | 1 | 259 | 21.22 |
| Jayme L. Szwarcfiter | 2 | 546 | 45.97 |