Results 231 to 240 of about 4,514 (260)

Minimum Cuts for Circular-Arc Graphs

SIAM Journal on Computing, 1990
Summary: The problem of finding a minimum cut of n arcs on a unit circle is considered. It is shown that this problem can be solved in \(\Theta\) (n log n) time, which is optimal to within a constant factor. If the endpoints of the arcs are sorted, the problem can be solved in linear time.
D. T. Lee, Majid Sarrafzadeh, Ying-Fung Wu   +2 more
openaire   +2 more sources

Longest Paths in Circular Arc Graphs

Combinatorics, Probability and Computing, 2004
It is shown that all maximum length paths of a connected circular arc graph, or a connected interval graph, have non-empty intersection.
Paul N. Balister, Ervin Györi, Jenö Lehel, Richard H. Schelp   +3 more
openaire   +1 more source

Algorithms on circular‐arc graphs

Networks, 1974
AbstractConsider a finite family of non‐empty sets. The intersection graph of this family is obtained by representing each set by a vertex, two vertices being connected by an edge if and only if the corresponding sets intersect. The intersection graph of a family of arcs on a circularly ordered set is called a circular‐arc graph.
openaire   +2 more sources

Parallel algorithms on circular-arc graphs

Information Processing Letters, 1990
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
BERTOSSI A. A, MORETTI, SABRINA
openaire   +3 more sources

Dominating sets and domatic number of circular arc graphs

Discrete Applied Mathematics, 1985
A dominating set of a graph G = (N,E) is a subset S of nodes such that every node is either in S or adjacent to a node which is in S. The domatic number of G is the size of a maximum cardinality partition of N into dominating sets.
BONUCCELLI, MAURIZIO ANGELO, Bonuccelli, Maurizio A.   +1 more
exaly   +2 more sources

Independent Sets in Circular-Arc Graphs

Journal of Algorithms, 1995
Summary: This paper presents a linear time algorithm for the independent set problem on circular-arc graphs, previous algorithms for this problem have assumed that the input is a set of circular-arcs and solve the problem in \(O (n)\) time. However, the fastest known algorithm for constructing the circular-arc representation from a set of adjacency ...
Wen-Lian Hsu, Jeremy P. Spinrad
openaire   +2 more sources

List Homomorphisms and Circular Arc Graphs

Combinatorica, 1999
The list homomorphism problem for a graph \(H\) has as input a graph \(G\) and lists \(L(v)\subseteq V(H)\) for the vertices \(v\in V(G)\). The output is a homomorphism \(f:G\to H\) with \(f(v)\in L(v)\) for every \(v\in V(G)\). It is shown that if \(H\) is loopless then this problem is polynomially solvable if \(\overline{H}\) is a circular arc graph ...
Tomás Feder, Pavol Hell, Jing Huang 0007   +2 more
openaire   +1 more source

Interval bigraphs and circular arc graphs

Journal of Graph Theory, 2004
AbstractWe prove that the complements of interval bigraphs are precisely those circular arc graphs of clique covering number two, which admit a representation without two arcs covering the whole circle. We give another characterization of interval bigraphs, in terms of a vertex ordering, that we hope may prove helpful in finding a more efficient ...
Pavol Hell, Jing Huang 0007
openaire   +1 more source

Two remarks on circular arc graphs

Graphs and Combinatorics, 1997
A graph \(G\) is said to be a circular arc graph if there exist circular arcs A\(g\), \(g\in V(G)\), such that \(g\), \(g'\) are adjacent in \(G\) if and only if the corresponding A\(g\), A\(_{g'}\) intersect. This paper shows that a graph with clique covering number two is a circular arc graph if and only if its edges can be coloured by two colours so
Pavol Hell, Jing Huang 0007
openaire   +2 more sources

Efficient algorithms for interval graphs and circular‐arc graphs

Networks, 1982
AbstractWe show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in O(n log n) time [O(n) time if the endpoints of the intervals are sorted].
Udaiprakash I. Gupta, D. T. Lee, Joseph Y.-T. Leung   +2 more
openaire   +2 more sources