Results 191 to 198 of about 184,697 (198)

A CHARACTERIZATION OF COMPARABILITY GRAPHS AND OF INTERVAL GRAPHS

Canadian Journal of Mathematics, 1964
Let < be a non-reflexive partial ordering defined on a set P. Let G(P, <) be the undirected graph whose vertices are the elements of P, and whose edges (a, b) connect vertices for which either a < b or b < a. A graph G with vertices P for which there exists a partial ordering < such that G = G(P, <) is called a comparability graph.In §
Alan J. Hoffman, P. C. Gilmore
openaire   +2 more sources

Recognizing d-Interval Graphs and d-Track Interval Graphs [PDF]

Algorithmica, 2010
A d-interval is the union of d disjoint intervals on the real line. A d-track interval is the union of d disjoint intervals on d disjoint parallel lines called tracks, one interval on each track. As generalizations of the ubiquitous interval graphs, d-interval graphs and d-track interval graphs have wide applications, traditionally to scheduling and ...
openaire   +1 more source

Interval graphs

1980
Publisher Summary This chapter discusses the properties, characterization, and theorems of interval graphs. The earliest characterization of interval graphs was obtained by Lekerkerker and Boland. Their result embodies the notion that an interval graph neither can branch into more than two directions nor can circle back onto itself. Theorem by Gilmore
openaire   +3 more sources

Interval graphs and maps of DNA

Bulletin of Mathematical Biology, 1986
A special class of interval graphs is defined and characterized, and an algorithm is given for their construction. These graphs are motivated by an important representation of DNA called restriction maps by molecular biologists. Circular restriction maps are easily included.
Michael S. Waterman, Jerrold R. Griggs
openaire   +3 more sources

Interval digraphs: An analogue of interval graphs

Journal of Graph Theory, 1989
AbstractIntersection digraphs analogous to undirected intersection graphs are introduced. Each vertex is assigned an ordered pair of sets, with a directed edge uv in the intersection digraph when the “source set” of u intersects the “terminal set” of v.
Aniruddha Roy, Malay K. Sen, Sandip Kumar Das, Douglas B. West   +3 more
openaire   +2 more sources

Dotted interval graphs

ACM Transactions on Algorithms, 2012
We introduce a generalization of interval graphs, which we call Dotted Interval Graphs (DIG). A dotted interval graph is an intersection graph of arithmetic progressions (dotted intervals). Coloring of dotted interval graphs naturally arises in the context of high throughput genotyping.
Moshe Lewenstein, Yonatan Aumann, Oren Melamud, Zohar Yakhini, Ron Y. Pinter   +4 more
openaire   +2 more sources

Separator Theorems for Interval Graphs and Proper Interval Graphs

2015
C.L.Monma and V.K.Wei [1986, J. Comb. Theory, Ser-B, 41, 141-181] proposed a unified approach to characterize several subclasses of chordal graphs using clique separator. The characterizations so obtained are called separator theorems. Separator theorems play an important role in designing algorithms in subclasses of chordal graphs.
openaire   +2 more sources

Characterizing interval graphs which are probe unit interval graphs

Discrete Applied Mathematics, 2019
Abstract A graph G is a probe unit interval graph if its vertex set can be partitioned into a set P of probe vertices and a stable set N of nonprobe vertices, so that a unit interval graph can be obtained by adding a set of edges whose endpoints belong to N .
openaire   +2 more sources