Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs
Ist Teil von
SIAM journal on computing, 1996-04, Vol.25 (2), p.390-403
Ort / Verlag
Philadelphia, PA: Society for Industrial and Applied Mathematics
Erscheinungsjahr
1996
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
Our main result is a linear-time (that is, time $O(m + n)$) algorithm to recognize and represent proper circular-arc graphs. The best previous algorithm, due to A. Tucker, has time complexity $O(n^2 )$. We take advantage of the fact that (among connected graphs) proper circular-arc graphs are precisely the graphs orientable as local tournaments, and we use a new characterization of local tournaments. The algorithm depends on repeated representation of portions of the input graph as proper interval graphs. Thus we also find it useful to give a new linear-time algorithm to represent proper interval graphs. This latter algorithm also depends on an orientation characterization of proper interval graphs. It is conceptually simple and does not use complex data structures. As a byproduct of the correctness proof of the algorithm, we also obtain a new proof of a characterization of proper interval graphs by forbidden subgraphs.