%DOMINATION PROBLEMS

@article(KeiSch92
,author=       {J. Mark Keil and Doug Schaefer}
,title=        "An optimal algorithm for finding dominating cycles in
		circular-arc graphs"
,journal=      "Discrete Applied Mathematics"
,annote=       "An $O(n \log n)$ algorithm for finding a minimum cardinality
		dominating cycle in an interval graph and in a circular-arc
		graph.

		It proves that under the algebraic computation tree
		computation model, $\Omega(n\log n)$ time is required to
		determine if a dominating cycle exists."
,vol=          36
,year=         1992
,pages=        "25-34")

@article(GupLeeLeu82
,author=       "U. I. Gupta and D. T. Lee and J. Y. T. Leung"
,title=        "Efficient algorithms for interval graphs and
		circular-arc graphs"
,journal=      "Networks"
,annote=       "An $O(n log n)$ algorithm for finding a maximum independent
		set, a minimum covering by disjoint completely connected
		sets or cliques, and a maximum clique in an interval graph
		given in the form of a family of intervals.  It runs in
		$O(n)$ if the endpoints of the intervals are sorted.

		$O(n ^ 2)$ to find a maximum independent  set and
		a minimum covering by disjoint completely connected sets
		or cliques in a circular-arc graph."
,vol=		12
,year=		1982
,pages= 	{459--467}
)

@article(	R88a
,author=        {Ramalingam,G.}
,title=         {Total domination in interval graphs revisited}
,annote=        {$O(n+m)$ algorithm for finding minimum cardinality
		total dominating set in an interval graph.}
,journal=       {Information processing letters}
,volume=	27
,number=	1
,year=		1988
,pages=         {17--21}
)

@article(	R88b
,author=        {Ramalingam,G.}
,title=         {A unified approach to domination problems on interval
		graphs}
,annote=        "$O(n+m)$ linear time algorithms for finding minimum
weight independent dominating set, dominating set, total dominating set
and connected dominating set in interval graphs."
,journal=       {Information processing letters}
,volume=	27
,number=	1
,year=		1988
,pages=         {271--274}
)

%CHARACTERISATION OF INTERVAL GRAPHS

@article(	H57
,author=        {Hajos,G.}
,title=         "Uber eine Art von Graphen"
,annote=        {First posed the problem of characterizing interval
graphs}
,journal=       {Intern. Math.}
,volume=	11
,year=		1957
)

@article(       LB62
,author=        {Lekkerkerker ,C. and Boland ,J.}
,title=         {Representation of a finite graph by a set of intervals
on the real line}
,journal=       {Fundamenta Math.}
,annote=	"Two criteria are proved for interval graphs.  Interval
graphs are characterised as those triangulated graphs which do not
possess an asteroidal triple.  Also, a characterization is derived by a
class of forbidden induced subgraphs."
,volume= 	51
,year=          1962
,pages=         {45--64}
)

@article(       Hal82 
,author=        {Halin ,R.}
,title=         {Some remarks on interval graphs}
,journal=       {Combinatorica}
,annote=	"Interval graphs are characterized as having the
property namely - among any three cliques there is always at least one
which separates the two others.

		Infinte interval graphs are characterized by a new form
		of decomposition generalizing consecutive simplicial
		decomposition.  It is also proved that a graph $G$ is
		an interval graph if and only if every finite induced 
		subgraph of $G$ is also one."

,volume=        2
,year=          1982
,pages=         {297--304}
)

@article(       FG65 
,author=        {Fulkerson ,D.R. and Gross ,O.A.}
,title=         {Incidence matrices and interval graphs}
,journal=       {Pacific Journal of Math.}
,annote=	"A characterization in terms of the incidence matrix
		is given for interval graphs.  It is proved that a graph
		$G$ is an interval graph if and only if the dominating
		clique versus incidence matrix of $G$ has the
		consecutive ones property."
,volume=	15
,year=          1965 
,pages=         {835--855}
)

@article(       GH64 
,author=        {Gilmore ,P.C. and Hoffman ,A.J.}
,title=         {A characterization of comparability graphs and of
		interval graphs}
,journal=       {Canadian Journal of Mathematics}
,annote=	"A characterization of the comparability and interval
		graphs is given.  A graph $G$ is an interval graph if
		and only if every quadrilateral in $G$ has a diagonal
		and every odd cycle in $G^{c}$ has a triangular chord.

		It is also determined that for any interval graph $G$
		the minimum cardinality of a linearly ordered set $O$
		for which there is a set of intervals $I$ such that
		$G=G(O,I)$."
,volume=	16
,year=          1964 
,pages=         {539--548}
)

@article(	Fis70
,author=        {Fishburn, Peter.C.1}
,title=         {An interval graph is not a comparability graph }
,annote=        {Provides an example to illustrate that interval graphs
are not necessarily comparability graphs.}
,journal=       {Journal of combinatorial theory}
,volume=	8
,year=		1970
,pages=         {442--443}
)

%RECOGNITION OF INTERVAL GRAPHS

@article(	LB76
,author=        {Lueker ,G.S. and Booth ,K.S.}
,title=         {Testing for the consecutive ones property, interval
graphs and the graph planarity using $PQ$ tree algorithm}
,journal=       {Journal of Computing System Sciences}
,annote=	"An $O(n+m)$ interval graph recognition algorithm 
is given which
		involves two phases namely - chordality test and
		a test for consecutive ones property.  A data structure
		called $PQ$ tree is introduced which helps solve the
		consecutive arrangement problem efficiently."
,volume=	13
,number=	3
,year=		1976
,pages=         {335--379}
)

@article(	KM89
,author=        {Korte,Norbert and Mohring, Rolf.H.}
,title=         {An incremental linear-time algorithm for recognizing
interval graphs}
,annote=	"A simpler $O(n+m)$ interval graph recognition algorithm
		which uses a more informative $PQ$ tree called the
		modified $PQ$ tree for the second phase." 
,journal=       {{SIAM} Journal of Computing}
,volume=	18
,number=	1
,year=		1989
,pages=         {68--81}
)

@article(	SIM91
,author=        {Simon,K.}
,title=         {A new simple linear algorithm to recognize interval
		graphs}
,journal=       {Computational geometry methods, algorithms and
applications, International Workshop}
,annote=	"A simpler $O(n+m)$ interval graph recognition algorithm
		which uses lexicographic breadth first search repeatedly
		for the second phase."
,year=		1991
,pages=         {289--308}
)

@article(	HSU92
,author=        {Hsu, Wen-lian}
,title=         {A simple test for interval graphs}
,annote=	"A simple linear time recognition algorithm for
		interval graphs is given.  This algorithm directly
		places the intervals without using maximal cliques
		like the others."
,journal=       {Graph-theoretic concepts in computer science}
,year=		1992
,pages=         {11--16}
)


%ISOMORPHISM OF INTERVAL GRAPHS

@article(   	LB79     
,author=        {Lueker ,G.S. and Booth ,K.S.}
,title=         {A linear time algorithm for deciding interval graph
isomorphism}
,annote=	"A linear time $O(n+m)$ interval graph isomorphism
		algorithm is given.  It is based on their  recognition
		algorithm of 1976.

		It is proved that chordal isomorphism is as hard as for
		general graphs."
,journal=       {Journal of the {ACM}}
,volume=	26
,year=          1979
,pages=         {183--195}
)

%PARALLEL ALGORITHMS

@article(	SP92
,author=        {Sprague,A.P. and Kulkarni,K.H.}
,title=         {Optimal parallel algorithms for finding cut vertices
and bridges of interval graphs}
,annote=        {$O(log n)$ time parallel algorithm in {EREW PRAM} model using 
		$(n / {\log} n)$ processors to find cut vertices, bridges and
		blocks for an  interval graph with n vertices and 
		ends presorted.  If the ends are not sorted, then the
		algorithm  is $O(\log n)$ time using $n$ processors.}
,journal=       {Information processing letters}
,volume=	42
,number=	4	
,year=		1992
,pages=		{229--234}
)

@inproceedings(	SG91
,author=        {Sridhar,M.A. and Goyal, S.}
,title=         {Efficient parallel computation of hamiltonian paths and
		circuits in interval graphs}
,booktitle=     {Proceedings of International Conference on parallel
		processing}
,volume=	3
,year=		1991
,pages=         {83--90}
,annote=        {$O(\log n)$ time parallel algorithm for finding
hamiltonian path and cycle in an interval graph using  $O(n \sp 2)$ 
processors on {EREW} model.}
)

@inproceedings( OSZ90 
,author=        {Olariu, S. and Schwing, J.L. and Zhang,J.}
,title=         {Optimal parallel algorithms for problems modelled by a
family of Intervals}
,booktitle=      {Proceedings of 28th Annual Allerton Conf. on
Communication, Control and Computing}
,year=          1990
,pages=         {282--291}
,annote=        {$O( \log n)$ time parallel algorithm for finding
maximum independent set, minimum clique cover, minimum dominating set,
center and the shortest path for an interval graph using  $O(n)$ 
processors on {EREW} model.}
)

@inproceedings( DS92 
,author=        {Das, Sajal.K. and Chen,Calvin.C.}
,title=         {Efficient parallel algorithms on
interval graphs}
,booktitle=      {Proceedings of 4th International {PARLE} Conference }
,year=          1992
,pages=         {131--143}
,publisher=	{Springer-Verlag}
,annote=        {$O(\log n)$ time parallel algorithms for finding
{BFS}-tree, {DFS}-tree, cut vertices, bridges and minimum coloring 
using $O(n)$ processors on {EREW PRAM} model.} 
,note=          ""
)

@article(	BB87
,author=        {Bertossi,A.A. and Bonuccelli,M.A.}
,title=         {Some Parallel Algorithms on Interval Graph}
,annote=        {$O(\log n)$ parallel algorithms for finding the 
maximum weighted clique, maximum weighted independent set, minimum
clique cover, minimum weighted dominating set using 
$O(n \sp 2 / \log n)$ processors on {CREW} model.}
,journal=       {Discrete Applied Mathematics}
,volume=	16
,year=		1987
,pages=         {101--111}
)

@inproceedings(	AP92
,author=	{Adhar,G.S. and Peng,S.}
,title=		{Parallel algorithms for finding connected, independent
and total domination in interval graphs}
,booktitle=	"Algorithms and Parallel VLSI Architectures II.
Proceedings of the Internation Workshop"
,publisher=	"Elsevier"
,year=		1992
,pages=		{85--90}
,annote=	"$O( \log n)$ time parallel algorithms to find connected
domination, independent domination and total domination sets in interval
graphs using $O(n (n / \log n))$ processors on CREW-PRAM model."
)

@inproceedings(	WC94
,author=	{Wang,Chi.Su. and Chang,Ruay.Shiung.}
,title=		{Parallel maximal cliques algorithms for interval graphs
with applications}
,booktitle=	"Proceedings of the 1994 International Symposium on
Parallel Architecture, Algorithms and Networks (ISPAN)"
,publisher=	"IEEE Comput. Soc. Press"
,year=		1994
,pages=		{89--96}
,annote=	"$O(n \log n)$ time algorithm for finding all maximal
cliques is given.  If implemented in parallel, it requires $O( \log n)$
time using $O(n^2)$ processors.  Using the relationship between
maximal cliques the all-pair shortest path problem is solved in 
$O( \log n)$ time using $O(n^2)$ processors."
)

%COLORING PROBLEMS

@article(	OL91
,author=        {Olariu, S.}
,title=         {Optimal greedy heuristic to color interval graphs}
,annote=        {A $O(n)$ algorithm for coloring interval graphs.
Interval graphs are characterised in terms of a linear order on their
vertices such that the greedy heuristic "always use the smallest
available color" yeilds an exact coloring algorithm for interval graphs.}
,journal=       {Information Processing letters}
,volume=	37
,number=	1
,year=		1991
,pages=         {21--25}
)

@article(	YUYA93
,author=        {Yu,Ming-Shing and Yang, Cheng.Hsing}
,title=         {A simple optimal parallel algorithm for the minimum
coloring problem on interval graphs}
,annote=        {$O(\log n)$ time parallel algorithm to find minimum
coloring on $O(n)$ processors on {EREW PRAM} given unsorted intervals.
If sorted, $O(\log n)$ time algorithm using $O(n / \log n)$ processors}
,journal=       {Information processing letters}
,volume=	48
,number=	1
,year=		1993
,pages=         {47--51}
)


%INDEPENDENT SET

@article(	JUYI92
,author=        {Ju,Yuan.Hsiao and Chuan,Yi.Tano.}
,title=         {An efficient algorithm for finding a maximum weight
2-independent set on interval graphs}
,annote=        {Introduces $O(n)$ time algorithm for solving the
maximum weight independent  set problem on an interval graph 
with $n$ vertices given
its interval representation with sorted endpoints.  Using this an 
$O(n \sp 2)$ time algorithm to solve maximum 2-independent set is
designed.}
,journal=       {Inforation processing letters}
,volume=	43
,number=	5
,year=		1992
,pages=         {229--235}
)

@article(        LEU84
,author=        {Leung, Joseph}
,title=         {Fast algorithm for generating all maximal independent
sets of interval, circular-arc and chordal graphs}
,annote=        {$O(n \sp 2 + \beta)$ time algorithms for generating all
maximal independent sets for interval and circular-arc graphs. $\beta$ is
the sum of the number of vertices of all maximal independent sets.}
,journal=       {Journal of algorithms }
,volume=	5
,number=	1
,year=		1984
,pages=         {22--35}
)

%MISCELLANEOUS 

@inproceedings( CPL93
,author=	{Chang,M.S. and Peng,S.L. and Liaw,J.L.}
,title=		{Deferred-Query -- an efficient approach for problems on
interval and circular-arc graphs}
,booktitle=	{Algorithms and Data Structures. Third Workshop.
{WADS'93}}
,year=		1993
,pages=		{223--233}
,annote=	{$O(n)$ time algorithms for the domatic partition,
		optimal path cover, Hamiltonian path, Hamiltonian
		circuit and matching problems on a set of sorted
		intervals.}
)

@article(	SG85	
,author=        {Skrien,D. and Gimbel,J.}
,title=         {Homogeneously  representable interval graphs}
,annote=        "Gives a characterization of interval graphs that can be
represented homogeneously in terms of forbidden induced subgraphs."
,journal=       {Discrete Mathematics}
,volume=	55
,year=		1985
,pages=         {213--216}
)

%PATH PROBLEMS

@inproceedings(	JSC93
,author=	{Joshi,D.S. and Sridhar,R. and Chandrasekharan,N.}
,title=		{Efficient algorithm for all-pair shortest path problem
on interval, directed path and circular-arc graphs}
,booktitle=	{Proceedings of {ICCI'}93. Fifth international
Conference on Computing and Information}
,year=		1993
,pages=		{31--35}
,annote=	"An algorithm for the all-pair shortest path problem
with time and space complexities of $O(n \sp 2)$ and $O(n)$ given a
sorted set of $n$ intervals.  Algorithms for the same problem are also 
given for directed path and circular-arc graphs." 
)

%MATCHING PROBLEMS

@inproceedings(	AACL95
,author=	{Andrews,M.G. and Atallah,M.J. and Chen,D.Z. and
Lee,D.T.}
,title=		{Parallel algorithms for maximum matching in interval
graphs}
,booktitle=	"Proceedings 9th Parallel Processing Symposium"
,publisher=	"IEEE Comput. Soc. Press"
,year=		1995
,pages=		{84--92}
,annote=	"An $O(\log \sp 3 n)$ time parallel algorithm for
finding maximum matchings among pairs of disjoint intervals in interval
graphs using $O(n / {\log \sp 2 n})$ processors on the {EREW PRAM} 
model and using $O(n)$ processors on the hypercubes." 
)

%PARTITION PROBLEMS

@inproceedings(	SP94
,author=	{Sprague, A.P.}
,title=		{Domatic partition of interval graphs}
,booktitle=	"Proceedings of the 32nd Annual Southeast Conference"
,publisher=	"ACM"
,year=		1994
,pages=		{227--232}
,annote=	"An $O(n)$ algorithm to construct a domatic partition 
given an interval graph in the interval model and its ends already
sorted." 
)

@article(	YUYA92
,author=        {Yu,Ming-Shing. and Yang,Cheng-Hsing.}
,title=         {An optimal parallel algorithm for the domatic partition
problem on an interval graph given its sorted model}
,annote=        "$O( \log n)$ time parallel algorithm for the domatic
partition problem using $O(n / \log n)$ processors on EREW PRAM model
given an $n$ intervals with endpoints sorted.  If the intervals are
unsorted, the algorithm takes $O( \log n)$ time on $O(n)$
processors."
,journal=       {Information Processing Letters}
,volume=	44
,number=	1
,year=		1992
,pages=         {15--22}
)


@article(	MA88
,author=        {Ma,Shao-Han.}
,title=         {Maximal cliques partitions of interval graphs}
,annote=        "This paper shows that if an interval graph possesses a
		maximal-clique partition then its clique covering and
		clique partition numbers are equal, and to the maximal
		clique kpartition number.  Moreover, an interval graph
		has such a partition if and only if all its maximal
		cliques are edge-disjoint."
,journal=       {Australian Mathematical Society Journal Series {A}}
,volume=	45
,number=	2
,year=		1988
,pages=         {227--232}
)

%HAMILTONIAN PATHS AND CYCLES

@inproceedings(	LGM94
,author=	{Liang, Y.D. and Greenlaw,R. and Manacher,G.}
,title=		{$NC^2$ algorithms regarding Hamiltonian paths and
circuits in interval graphs}
,booktitle=	"Parallel and Distributed Computing, Theory and
Practice.  First Canada-France Conference"
,publisher=	""
,year=		1994
,pages=		{45--57}
,annote=	"$O(\log^2 n)$ time parallel algorithm for finding
Hamiltonian path in an interval graph using $n$ processors on the 
EREW PRAM model.  $O(\log^2 n)$ time algorithm for finding Hamiltonian
cycle using $n^2$ processors.  If the intervals are presorted, the 
parallel approach taken here leads to
an $O(n \alpha (n))$ sequential algorithm where $ \alpha (n)$ is the
inverse of Ackermann's function."
)

@article(	MRR92
,author=        {Marathe,M.V. and Ravi and Rangam}
,title=         {Generalized vertex covering}
,annote=        {Given an integer $i$ and a graph $G$, i-vertex cover
problem is to find a minimum set of vertices such that all cliques in
$G$ of size $i$ contain atleast one vertex form this set.  This paper
presents a greedy linear time algorithm for this problem in interval
graphs.}
,journal=       {Discrete Applied Mathematics}
,volume=	39
,number=	1
,year=		1992
,pages=         {87--93}
)