@article(Jun89, author= "Douglas Jungreis", title= "Hamiltonian paths in Cayley digraphs of finitely-generated infinite abelian groups.", journal= "Discrete Mathematics", annote= "It proves that for every strongly connected Cayley digraph on a finitely generated, infinite abelian group there is a minimal generating set whose Cayley digraph has either a 1-way or 2-way infinite Hamiltonian path.", vol= 78, year= "1989", pages= "95-104") @article(ManManSmi90, author= "Glenn K. Manacher and Terrance A. Mankus and Carol Joan Smith", title= "An optimum $\Theta(n\log n)$ algorithm for finding a cononical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals.", journal= "Information Processing Letters", annote= "", vol= 35, year= "1990", pages= "205-211") @article(SchHak88, author= "E. F. Schmeichel and S. L. Hakimi", title= "A cycle structure theorem for Hamiltonian graphs", journal= "Journal of Combinatorial Theory, Series B.", annote= "It is proved that if $x$ and $y$ are consecutive vertices in a Hamilton cycle of a graph on $n$ vertices and if the sum of the degrees of $x$ and $y$ is at least $n$ then the graph is pancyclic, bipartite, or misses only an $(n-1)$-cycle.", vol= 45, year= "1988", pages= "99-107") @article(She91, author= "F. Bruce Shepherd", title= "Hamiltonicity in claw-free graphs", journal= "Journal of Combinatorial Theory, Series B.", annote= "A structural result about claw-free, net-free graphs is found and a simplified proofs of theorems that every connected(or 2-connected), claw-free, net-free grpah has a Hamilton path(or Hamilton cycle, respectively) is given. It is also proved that every 3-connected, claw-free, net-free graph is Hamilton connected.", vol= 53, year= "1991", pages= "173-194") @article(Wei93, author= "Bing Wei", title= "Hamiltonian paths and Hamiltonian connectivity in graphs", journal= "Discrete Mathematics", annote= "If $G$ is a 2-connected graph with $n$ vertices such that $d(u)+d(v)+d(w)-\vert N(u)\cap N(v)\cap N(w)\vert \geq n+1$ holds for any triple of independent vertices $u$, $v$, $w$, then for any distinct vertices $u$ and $v$ such that $\{u, v\}$ is not a cut vertex set of $G$, there is a Hamiltonian path between $u$ and $v$. In particular, if $G$ is 3-connected, then $G$ is Hamiltonian connected.", vol= 121, year= "1993", pages= "223-228") @article(BolBri93, author= "Bela Bollobas and Graham Brightwell", title= "Cycles through specified vertices", journal= "Combinatorica. An International Journal on Combinatorics and the Theory of Computing", annote= "If $G$ is a graph with $n$ vertices and let $W$ be a set of $w\geq 3$ vertices of degree at least $d\geq 1$ and assume that $t\colon = \lceil w/(\lceil n/d\rceil-1)\rceil \geq 3$, then there is a cycle in $G$ passing through at least $t$ vertices of $W$.", Vol= 13, year= "1993", pages= "147-155") @article(MulNic93, author= "Haiko Muller and Falk Nicolai", title= "Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs.", journal= "Information Processing Letters", annote= "Polynomial time algorithms for the Hamiltonian circuit and Hamiltonian path problems in $(6,2)$-chordal bipartite graphs is developed by investigating the neighbourhood of the last pendant vertex in a one-vertex extension sequence.", vol= 46, year= "1993", pages= "225-230") @article(FavMagMauOrd93, author= "Odile Favaron and Pedro Mago and Consuelo Maulino and Oscar Ordaz", title= "Hamiltonian properties of bipartite graphs and digraphs with bipartite independence $2$", journal= "SIAM Journal on Discrete Mathematics", annote= "Let $G$ be a bipartite graph in which $\alpha\sb {\rm BIP}(G)$, the maximum order of an induced balanced bipartite subgraph without edges, is equal to $2$. When its order is at least 10, it is shown that $G$ contains a Hamiltonian path, provided that it is connected, and that, if its minimum degree is at least $2$, then it is bipancyclic.", vol= 6, year= "1993", pages= "189-196") @article(CheYes93, author= "Lin Chen and Yaacov Yesha", title= "Efficient parallel algorithms for bipartite permutation graphs.", journal= "Networks: An International Journal", annote= "An $O(\log\sp 2n)$ algorithm with $O(n\sp 3)$ processors on a common CRCW PRAM is given to solve these problems on bipartite permutaion graphs: transforming a bipartite graph into a strongly ordered one if it is also a permutation graph; testing isomorphism; finding a Hamiltonian path/cycle; solving a variant of the crossing number problem. It is also shown that a minimum fill-in problem for bipartite permutation graphs can be solved efficiently by a randomized parallel algorithm.", vol= 23, year= "1993", pages= "29-39") @article(Nar89, author= "Giri Narasimhan", title= "A note on the Hamiltonian circuit problem on directed path graphs", journal= "Information Processing Letters", annote= "It proves that the Hamiltonian circuit problem and the Hamiltonian path problem are NP-complete on directed path graphs", vol= 32, year= "1989", pages= "167-170") @article(ItaPapSzw82, author= "Alon Itai and Christos H. Papadimitriou and Jayme Luiz Szwarcfiter", title= "Hamilton Paths in Grid Graphs", journal= "SIAM Journal on Computer", annote= "Given a rectangular grid graph and two of its nodes, the authors give necessary and sufficient conditions for the graph to have a Hamilton path between these two nodes and the Hamilton path problem for general grid graphs is shown to be NP-complete.", rthe vol= 11, year= "1982", pages= "676-686") @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 grpah. 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(HsuTsa91, author= "Wen-Lian Hsu and Kuo-Hui Tsai", title= "Linear time algorithms on circular-arc graphs", journal= "Information Processing Letters", annote= "An $O(n)$ algorithm sloves the maximum independent set, the minimum clique cover and the minimum dominating set problems simultaneously(unweighted version).", vol= 40, year= 1991, pages= "123-129") @article(BerMor90, author= "Alan A. Bertossi and Sabrina Moretti", title= "Parallel Algorithms on Circular-arc Graphs", journal= "Information Processing Letters", annote= "$O(log^2 n)$ parallel algorithm for finding a maximum weighted clique with $O(n\sp 4 /\log n )$ processors, a maximum weighted independent set, a minimum weighted dominating set and a minimum weighted total dominating set of a circular-arc graph by using $O(n\sp 3 /\log n)$ processors and a a shared memory model(SMM) of parallel computers. $O(n ^ 3)$ sequential algorithm for the minimum weighted dominating set and minimum weighted total dominating set problems.", vol= 33, year= 1990, pages= "275-281") @article(LeeSarWu90, author= "D. T. Lee and M. Sarrafzadeh and Y. F. Wu", title= "Minimum Cuts for Circular-arc Graphs", journal= "SIAM Journal on Computing", annote= "An $O(n log n)$ algorithm for finding a minimum cut of n arcs on a unit circle. Linear time if the endpoints of the arcs are sorted. Linear time to solve the maximum independent set of {\it n} arcs too under this condition.", vol= 19, year= 1990, pages= "1041-1050") @article(Tuc74, author= "Alan Tucker", title= "Structure Theorems for Some Circular-arc Graphs", journal= "Discrete Mathematics", annote= "This paper presents structure theorems for proper circular-arc graphs and for unit circular-arc grpahs", vol= 7, year= 1974, pages= "167-195") @article(Tuc75, author= "Alan Tucker", title= "Coloring a family of circular arcs", journal= "SIAM Journal on Applied Mathematics", annote= "The strong perfect graph conjecture is valid for circular-arc graphs. The problem of determining whether a family of arcs can be k-colored is converted into a multicommodity flow problem.", vol= 29, year= 1975, pages= "") @article(Tuc80, author= "Alan Tucker", title= "An Efficient Test for Circular-arc Graphs", journal= "SIAM Journal on Computing", annote= "An $O(n ^ 3)$ algorithm for testing if a {\it n}-vertex graph is a circular-arc graph.", vol= 9, year= 1980, pages= "1-24") @article(ShiCheHsu92, author= "Wei-Kuan Shih and T. C. Chern and Wen-Lian Hsu", title= "An $O(n^2 log n)$ algorithm for the Hamiltonian cycle problem on circular-arc graphs", journal= "SIAM Journal on Computing", annote= "An $O(n\sp 2 log n)$ algorithm for the Hamiltonian cycle problem in a given circular-arc graph.", vol= 21, year= 1992, pages= "1026-1046") @inproceedings(EscSpi93, author= "Elaine M. Eschen and Jeremy P. Spinrad", title= "An $O(n\sp 2)$ algorithm for circular-arc graph recognition", booktitle= "Collection: Proceedings of the Fourth Annual ACM-SIAM symposium on discrete algorithms(Austin, TX, 1993)", year= 1993, pages= "128-137", publisher= "ACM, New York", annote= "An $O(n\sp 2)$ algorithm for recognizing circular-arc graph. It also gets an $O(n\sp 2)$ time isomorphism test for circular-arc graphs.", note= "") @article(Asa93, author= "Takao Asano", title= "Dynamic programming on intervals", journal= "International Journal of Computational Geometry and Applications", annote= "An $O(m\log n)$ algorithm for partitioning a graph. Also an $O(n\log n)$ algorithm for finding a minimum weigh dominating set of an interval graph and an $O(m\log n)$ algorithm for finding a maximum weight clique of a circular-arc graph are given.", vol= 3, year= 1993, pages= "323-330") @article(KasMas91, author= "Toshinobu Kashiwabara and Sumio Masuda", title= "Polynomial time algorithms on circular-arc overlap graphs", journal= "Networks", annote= "An $O(n\sp 2)$ algorithm for finding a maximum independent set and an $O(n\sp 5)$ algorithm for finding a maximum clique in a circular-arc overlap graph with $n$ arcs.", vol= 21, year= 1991, pages= "195-203") @article(MasNak88, author= "Sumio Masuda and Kazuo Nakajima", title= "An optimal algorithm for finding a maximum independent set of a circular-arc graph", journal= "SIAM Journal on Computing", annote= "An $O(n \log n)$ algorithm for finding a maximum independent set of a circular-arc graph in $O(n)$ space is provided. If the endpoints of the arcs are sorted, it will run in $O(n)$ time.", vol= 17, year= 1988, pages= "41-52") @article(RaoPan89, author= "A. Srinivasa Rao and Rangan C. Pandu", title= "Optimal parallel algorithms on circular-arc graphs", journal= "Information Processing Letters", annote= "To finding an (unweighted) maximum independent set, a minimum clique cover and a minimum dominating set on circular-arc grphs, a parallel algorithms running in $O(\log n)$ time with $O(n/\log n)$ processors using the EREW PRAM model is presented.", vol= 33, year= 1989, pages= "147-156") @article(KasMasNakFuj92, author= "Toshinobu Kashiwabara and Sumio Masuda and Kazuo Nakajima and Toshio Fujisawa", title= "Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph", journal= "Journal of Algorithms", annote= "An $O(n\sp {2.5}\, +$(output size)) algorithm for generating all maximum independent sets of a bipartite graph is given. It also presents an $O(n\sp {3.5}\,+$ (output size)) algorithm that generates all maximum cliques of a circular-arc graph.", vol= 13, year= 1992, pages= "161-174") @article(Kim90, author= "Sung Kwon Kim", title= "A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle", journal= "Information Precessing Letters", annote= "To find a maximum clique of a circular-arc graph, a parallel algorithm runs in $O(\log\sp 2n)$ time using $O(n\sp 3/\log n)$ processors in the CREW PRAM model is presented.", vol= 34, year= 1990, pages= "235-241") @article(ShiHsu89, author= "Wei Kuan Shih and Wen Lian Hsu", title= "An $O(n\log n+m\log\log n)$ maximum weight clique algorithm for circular-arc graphs", journal= "Information Precessing Letters", annote= "An $O(n\log n+m\log\log n)$ algorithm is given to solve the weighted case of the maximum weight clique problem.", vol= 31, year= 1989, pages= "129-134") @article(ApoHam89, author= "Alberto Apostolico and Susanne E. Hambrusch", title= "Finding maximum cliques on circular-arc graphs in $O(n\sp 2 \log\log n)$ ", journal= "Information Precessing Letters", annote= "An $O(n\sp 2 \log\log n)$ algorithm is given to solve the unweighted case of the maximum-sized clique problem.", vol= 26, year= 1987, pages= "209-215") @article(Gav74, author= "F. Gavril", title= "Algorithms on circular-arc graphs", journal= "Networks", annote= "An $O(n\sp 4)$ algorithm for finding a maximum independent set. An $O(n\sp 5)$ algorithm for finding a minimum covering by cliques, and an $O(n\sp 3)$ algorithm for finding a maximum clique of a circular-arc graph.", vol= 4, year= 1974, pages= "357-369") @article(Tuc71, author= "Alan Tucker", title= "Matrix Characterizations of Circular-arc Graphs", journal= "Pacific Journal of Mathematics", annote= "Circular-arc graphs' adjacency matrix has the quasi-circular 1's property", vol= 39, year= 1971, pages= "535-545") @article(Kle69, author= "Victor Klee", title= "What are the intersection graphs of arcs in a circle?", journal= "American Mathematics Monthly", annote= "Poses the circular-arc characterization and recognition problems", vol= 76, year= 1969, pages= "810-813") @Inproceedings(Tuc76, author= "Alan Tucker", title= "Circular arc graphs: new uses and a new algorithm", booktitle= "Theory and Applications of Graphs Proceedings, Michigan 1976", annote= "An $O(n ^ 4)$ algorithm for testing if a {\it n}-vertex graph is a circular-arc graph.", year= 1976) @unpublished(ShiHsu95, author= "Wei-Kuan Shih and Wen-Lian Hsu", title= "An Approximation Algorithm for Coloring Circular-arc Graphs", note= "between 1987 and 1993", annote= "An coloring algorithm which uses no more than $\alpha$ $\cdot$ q colors, where $\alpha$ = 5/3 and q is the size of a maximum clique in F.") @incollection(AtaCheLee93A, author= "Mikhail J. Atallah and Danny Z. Chen and D. T. Lee", title= "An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications", booktitle= "Collection: Algorithms--ESA '93", year= "1993", publisher= "Springer, Berlin", pages= "13-24") @incollection(AtaCheLee93B, author= "Mikhail J. Atallah and Danny Z. Chen and D. T. Lee", title= "Computing the all-paris longest chains in the plane.", booktitle= "Collection: Algorithms--ESA '93", year= "1993", publisher= "Springer, Berlin", pages= "1-13") @article(LiaRhe93, author= "Y. Daniel Liang and Chongkye Rhee", title= "Finding a maximum matching in a circular-arc graph", journal= "Information Processing Letters", annote= "An $O(n\log n)$ algorithm for finding a maximum matching in a circular-arc graph.", vol= 45, year= "1993", pages= "185-190") @article(AriPan91, author= "Srinivasa R. Arikati and C. Pandu Rangan", title= "Efficient reduction for path problems on circular-arc graphs", journal= "BIT. Computer Science Numberical Mathematics", annote= "An $O(n+m)$ algorithm for the parity path problem on proper circular-arc graphs, and $O(n\cdot m)$ algorithm for the parity path problem on circular-arc graphs.", vol= 31, year= "1991", pages= "182-193") @article(SenDasWes89, author= "M. Sen and S. Das and Douglas B. West", title= "Circular-arc digraphs: a characterization", journal= "Journal of Graph Theory", annote= "It gives matrix characterization of interval digraphs and circular-arc digraphs.", vol= 13, year= "1989", pages= "581-592") @article(Spi88, author= "Jeremy Spinrad", title= "Circular-arc graphs with clique cover number two", journal= "Journal of Combinatorial Theory Series B", annote= "It shows that problems on circular-arc graphs can be partitioned into two cliques are reducible to problems on two dimensional partial orders. It simplify the recognition algorithm by Tuc80 and the algorithm for determining whether two circular-arc graphs are isomorphic.", vol= 44, year= "1988", pages= "300-306") @incollection(SriPan89, author= "A. Rao Srinivasa and Rangan C. Pandu", title= "Linear algorithms for parity path and two path problems on circular-arc graph", booktitle= "Collection: Algorithms and data structures, (ottawa, ON, 1989)", year= "1989", publisher= "Springer, Berlin", pages= "267-290") @article(Dam93, author= "Peter Damaschke", title= "Paths in interval graphs and circular arc graphs", journal= "Discrete Mathematics", annote= "An $O(n\sp 5)$ algorithm for finding Hamiltonian paths in circular arc graphs.", vol= 112, year= "1993", pages= "49-64") @article(Ham88, author= "Golumbic Hammer", title= "Stability in circular-arc graphs", journal= "Journal on Algorithm", annote= "", vol= 9, year= "1988", pages= "314-320") @article(HsuSpi95, author= "Wen-Lian Hsu and Jeremy P. Spinrad", title= "Independent Sets in Circular-Arc Graphs", journal= "Journal of Algorithms", annote= " When the circular-arc graph is given as a set of adjacency lists, the independent set problem can be solved in $O(n + m)$ time.", vol= 19, year= "1995", pages= "145-160") @article(ReaRotUrr82, author= "R. C. Read and D. Rotem and J. Urrutia", title= "Orientations of circle graphs", journal= "Journal of Graph Theory", annote= "Discusses a certain type of orientation of a circle graph that arises from a given circle diagram.", vol= 6, year= 1982, pages= "325-341") @article(RotUrr81, author= "D. Rotem and J. Urrutia", title= "Finding maximum cliques in circle graphs", journal= "Networks", annote= "An $O(n^2)$ algorithm for finding a maximum clique; can also be used to find all maximum cliques in $O(n^2 + \gamma )$ time, where $\gamma$ is the sum of the sizes of all maximum cliques. A circle intersection model is assumed to be given.", vol= 11, year= 1981, pages= "269-278") @article(MasNakKasFuj90, author= "Sumio Masuda and Kazuo Nakajima and Toshinobu Kashiwabara and Toshio Fujisawa", title= "Efficient algorithms for finding maximum cliques of an overlap graph", annote= "Two algorithms: one finds a maximum clique in $O(n log n + min \{ m , n \omega \})$ time; the other finds all maximum cliques in $O( n log n + m + \gamma )$, where $\gamma$ is the sum of the sizes of all maximum cliques. An interval overlap model is assumed to be given.", journal= "Networks", vol= 20, year= 1990, pages= "157-171") @article(GarJohMilPap80, author= "M. R. Garey and D. S. Johnson and G. L. Miller and C. H. Papadimitriou", title= "The complexity of coloring circular arcs and chords", journal= "SIAM Journal on Algebraic and Discrete Methods", annote= "The following problems are shown to be {NP}-complete: the word problem for products of symmetric groups, the register allocation problem, the problem of realizing a permutation with parallel stacks, circular-arc graph coloring, and circle graph coloring. It is also shown that circular-arc graph $k$-colorability is solvable in $O( n k! k log k )$ time.", vol= 1, year= 1980, pages= "216-227") @incollection(EveIta71, author= "S. Even and A. Itai", title= "Queues, stacks and graphs", booktitle= "Theory of Machines and Computations", editor= "Z. Kohavi and A. Paz", annote= "The problem of sorting a permutation using queues or stacks in parallel, and a connection to the coloring problems on permutation and circle graphs.", publisher= "Academic Press", year= 1971, pages= "71-86") @incollection(SzwBar89, author= "Jayme L. Szwarcfiter and Magali M. A. Barroso", title= "Enumerating the maximal cliques of a circle graph", booktitle= "Graph theory, combinatorics, algorithms, and applications", editor= "Yousef Alavi and Fan R. K. Chung and Ronald L. Graham and D. Frank Hsu", annote= "An algorithm for generating all maximal cliques of a circle graph in $O(n(m+ \alpha ))$ time, where $\alpha$ is the number of maximal cliques in the graph. Locally edge transitive orientations of circle graphs are used. They also show that the number of maximal cliques in a circle graph graph can be computed in $O(nm)$ time.", publisher= "SIAM", year= 1989, pages= "511-517") @incollection(Ung88, author= "Walter Unger", title= "On the $k$-colouring of circle graphs", booktitle= "{STACS} 88: Fifth annual symposium on the theoretical aspects of computer science, {B}ordeaux, {F}rance, {F}ebruary 11-13, 1988 {P}roceedings", editor= "R. Cori and M. Wirsing", annote= "The $k$-colouring problem for circle graphs is {NP}-complete, for $k \geq 4$. Every circle graph is $2 \omega$ colourable, and such a colouring can be found in $O(n log n)$ time. The $k$-colouring problem for circle graphs is polynomially solvable if the graph has bounded degree.", publisher= "Springer-Verlag", address= "Berlin", series= "Lecture Notes in Computer Science", volume= 294, year= 1988, pages= "61-72") @article(Naj85, author= "Walid Naji", title= "Reconnaissance des graphes de cordes", journal= "Discrete Mathematics", annote= "Gives an $O(n^9)$ algorithm for circle graph recognition, using a certain orientation of the edges of a graph and a double labelling of the edges of the complement.", vol= 54, year= 1985, pages= "329-337") @article(Luc94, author= "Tomasz Luczak", title= "On the clique number of a random overlap graph", journal= "Journal of Applied Probability", vol= 31, year= 1994, pages= "582-588") @article(Gya85, author= "A. Gyarfas", title= "On the chromatic number of multiple interval graphs and overlap graphs", journal= "Discrete Mathematics", vol= 55, year= 1985, pages= "161-166") @article(BucGol83, author= "Mark A. Buckingham and Martin Charles Golumbic", title= "Partitionable graphs, circle graphs, and the {B}erge strong perfect graph conjecture", journal= "Discrete Mathematics", annote= "The strong perfect graph conjecture holds for $K_{1,3}$-free graphs and for circle graphs.", vol= 44, year= 1983, pages= "45-54") @unpublished(Buc81, author= "Mark A. Buckingham", title= "Efficient stable set and clique finding algorithms for overlap graphs", annote= "$O(n^2)$ algorithms for finding maximum independent sets and maximum cliques in circle graphs, given the interval representation.", school= "Department of Computer Science, New York University", note= "", year= 1981) @article(Kei93, author= "J. Mark Keil", title= "The complexity of domination problems in circle graphs", journal= "Discrete Applied Mathematics", annote= "The following problems are shown to be {NP}-complete for circle graphs: dominating set, connected dominating set, total dominating set. An $O(nm)$ algorithm is given for computing a minimum dominating clique in a circle graph.", vol= 42, year= 1993, pages= "51-63") @article(ApoAtaHam92, author= "Alberto Apostolico and Mikhail J. Atallah and Susanne E. Hambrusch", title= "New clique and independent set algorithms for circle graphs", journal= "Discrete Applied Mathematics", annote= "The following algorithms for circle graphs are presented, assuming an interval representation is given: an $O(n log n + min\{ m , n \omega log ( 2n / \omega ) \})$ algorithm for finding a maximum clique, an $O(n log n + min\{ n^2 , m log log n \})$ algorithm for finding a maximum weight clique, an $O(n log n + dn )$ time and space algorithm for finding a maximum weight independent set, where $d$ is the maximum number of intervals crossing any point in the given interval model.", vol= 36, year= 1992, pages= "1-24") @article(Bou87C, author= "Andr\'{e} Bouchet", title= "Reducing prime graphs and recognizing circle graphs", journal= "Combinatorica", annote= "Proves that every prime (in the sense of Cunningham) graph with $n>5$ vertices ``contains'' a prime graph with $n-1$ vertices. Gives an $O(n^5)$ recognition algorithm for circle graphs.", vol= 7, year= 1987, pages= "243-254") @article(Bou87D, author= "Andr\'{e} Bouchet", title= "Unimodularity and circle graphs", journal= "Discrete Mathematics", annote= "Proves that the adjacency matrix of a circle graph with a Naji orientation satisfies a unimodularity property.", vol= 66, year= 1987, pages= "203-208") @article(Bou94, author= "Andr\'{e} Bouchet", title= "Circle graph obstructions", annote= "$G$ is a circle graph if and only if no graph locally equivalent to $G$ has an induced subgraph isomorphic to one of three graphs.", journal= "Journal of Combinatorial Theory Series B", vol= 60, year= 1994, pages= "107-144") @article(Gav73, author= "F. Gavril", title= "Algorithms for a maximum clique and a maximum independent set of a circle graph", journal= "Networks", annote= "$O(n^3)$ algorithms for finding maximum independent sets and maximum cliques in circle graphs, given the interval representation.", vol= 3, year= 1973, pages= "261-273") @article(deF84, author= "Hubert de Fraysseix", title= "A characterization of circle graphs", journal= "European Journal of Combinatorics", annote= "A connected graph is a circle graph if and only if it is a cocyclic-path intersection graph.", vol= 5, year= 1984, pages= "223-238") @article(Fou78, author= "Jean-Claude Fournier", title= "Une charact\'{e}risation des graphes de cordes", journal= "C. R. Acad. Sc. Paris", annote= "A characterization of circle graphs is given in terms of order relations.", vol= "286{A}", year= 1978, pages= "811-813") @article(Hsu88, author= "Wen-Lian Hsu", title= "$O(mn)$ algorithms for the recognition and isomorphism problems on circular-arc graphs", journal= "SIAM Journal on Computing", annote= "The following algorithms are given (all of complexity $O(mn)$): circular-arc graph recognition and isomorphism and circle graph isomorphism.", year= 1988, note= "To appear") @article(GabSupHsu89, author= "Csaba P. Gabor and Kenneth J. Supowit and Wen-Lian Hsu", title= "Recognizing circle graphs in polynomial time", journal= "Journal of the ACM", annote= "An $O(nm)$ algorithm for circle graph recognition.", vol= 36, year= 1989, pages= "435-473") @article(Hsu85, author= "Wen-Lian Hsu", title= "Maximum weight clique algorithms for circular-arc graphs and circle graphs", journal= "SIAM Journal on Computing", annote= "An $O( n^2 + m log log n )$ algorithm for finding maximum weight cliques in circle graphs, and an $O( mn )$ algorithm for finding maximum weight cliques in circular-arc graphs.", vol= 14, year= 1985, pages= "224-231") @article(Spi94, author= "Jeremy Spinrad", title= "Recognition of circle graphs", journal= "Journal of Algorithms", annote= "An $O(n^2)$ algorithm for circle graph recognition.", vol= 16, year= 1994, pages= "264-282") @article(Dam89, author= "Peter Damaschke", title= "The {H}amiltonian circuit problem for circle graphs is {NP}-complete", journal= "Information Processing Letters", annote= "Proves that the {H}amiltonian cycle and {H}amiltonian path problems are {NP}-complete for circle graphs.", vol= 32, year= 1989, pages= "1-2") @unpublished(Ung91, author= "Walter Unger", title= "3-colouring circle graphs in polynomial time", year= 1991, note= "Private communication") @article(Llo89, author= "Errol L. Lloyd", title= "A Fast Algorithm for Finding Interlocking Sets", journal= "Information Processing Letters", annote= "Given an interval representation for a circle grpah, finds the connected componets in time $O(n \alpha (m))$ if interval endpoints are sorted, or $O(n log n)$ otherwise. This is also known as the problem of finding interlocking sets.", vol= 32, year= 1989, pages= "47-50") @unpublished(OlaZom95, author= "Stephan Olariu and Albert Y. Zomaya", title= "A Time- and Cost-Optimal Algorithm for Interlocking Sets, with Applications", annote= "Proves lower bound or computing connected components of circle graphs from the interested model: $O(nlogn)$ (sequential) or $O(logn)$ (parallel) and gives matching optimal algorithm. The sequential algorithm operates in $O(n)$ if interval endpoints are sorted. This is known as the problem of finding interlocking sets.", year= 1995, note= "Private communication") @ARTICLE {HS58, AUTHOR = "A. Haknal and J. Suranyi", TITLE = "Uber die Auflosung von Graphen in vollstandige Teilgraphen", JOURNAL = "Ann. Univ. Budapest, Eotvos Sect. Math 1", YEAR = "1958", PAGES = "113-121", } @ARTICLE {Duc76, AUTHOR = "P. Duchet", TITLE = "Propriete de Helly et problems de representation", JOURNAL = "Colloqu. Internat. CNRS 260, Problemes Combinatoires et Theorie du Graphs; Orsay France", YEAR = "1976", PAGES = "117-118", } @ARTICLE {Fla78, AUTHOR = "C.Flament", TITLE = "Hypergraphs arbores", JOURNAL = "Discrete Math. 21", YEAR = "1978", PAGES = "223-226", } @ARTICLE {RTL76, AUTHOR = "D.J. Rose; R.E. Tarjan and G.S. Lueker", TITLE = "Algorithmic aspects of vertex elimination of graph", JOURNAL = "SIAM J. Comput. 5", YEAR = "1976", PAGES = "266-283", } @ARTICLE {TY84, AUTHOR = "R.E. Tarjan and M. Yannakakis", TITLE = "Simple linear time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs.", JOURNAL = "SIAM J. Comput. 13", YEAR = "1984", PAGES = "566-576", } @ARTICLE {Hay85, AUTHOR = "R.B. Hayward", TITLE = "Weakly triangulated graphs", JOURNAL = "J. Comb. Theory (B) 39", YEAR = "1985", PAGES = "200-208", } @ARTICLE {HHM89, AUTHOR = "R.B. Hayward; C. Hoang and F. Maffray", TITLE = "Optimizing weakly triangulated graphs", JOURNAL = "Graphs and Combinatorics 5", YEAR = "1989", PAGES = "339-349", } @ARTICLE {Far83, AUTHOR = "M. Farber", TITLE = "Characterizations of strongly chordal graphs", JOURNAL = "Discrete Math. 43", YEAR = "1983", PAGES = "173-189", } @ARTICLE {Far84, AUTHOR = "M. Farber", TITLE = "Domination, independent domination and duality in strongly chordal graphs", JOURNAL = "D. A. M. 7", YEAR = "1984", PAGES = "115-130", } @ARTICLE {PT86, AUTHOR = "R. Paige and R.E. Tarjan", TITLE = "Three partition refinement algorithms.", JOURNAL = "SIAM J. Comp Vol 16 No 5", YEAR = "1986", } @ARTICLE {Spi88b, AUTHOR = "J.P. Spinrad", TITLE = "Doubly lexical ordering of dense 0-1 matrices", JOURNAL = "SIAM J. Comput.", YEAR = "1988", } @ARTICLE {Gol80, AUTHOR = "M.C. Golumbic", TITLE = "Algorithmic Graph Theory and Perfect Graphs.", JOURNAL = "Academic Press", YEAR = "1980", } @ARTICLE {Gol88, AUTHOR = "M.C. Golumbic", TITLE = "Algorithmic aspects of intersection graphs and representation hypergraphs", JOURNAL = "Graphs and Combinatorics 4", YEAR = "1988", PAGES = "307 - 321", } @ARTICLE {Bra91, AUTHOR = "A. Brandstadt", TITLE = "Classes of biparties graphs related to chordal graphs", JOURNAL = "D. A. M. 32", YEAR = "1991", PAGES = "51-60", } @ARTICLE {Bra92, AUTHOR = "A. Brandstadt", TITLE = "Special Graph Classes - A Survey (revised version)", JOURNAL = "Technical Report SM-DU-204, Univ Duisburg", YEAR = "1992", } @ARTICLE {DPC, AUTHOR = "F.F. Dragan; C.F. Prisacaru and V.D. Chepoi", TITLE = "Location problems in graphs and the Helly property", JOURNAL = "Diskretnaja Matematika", YEAR = "1992", } @ARTICLE {BB92, AUTHOR = "H. Behrendt and A. Brandstadt", TITLE = "Domination and the use of maximum neighbourhoods", JOURNAL = "Technical Report SM-DU-204, Univ Duisburg", YEAR = "1992", } @ARTICLE {Mos92, AUTHOR = "M.Moscarini", TITLE = "Doubly Chordal graphs, Steiner trees and connected domination", JOURNAL = "Networks", YEAR = "1992", } @ARTICLE {GC78, AUTHOR = "M.C. Golumbic and C.F. Goss", TITLE = "Perfect elimination and chordal bipartite graphs", JOURNAL = "J. Graph Theory 2", YEAR = "1978", PAGES = "155-163", } @ARTICLE {Dir61, AUTHOR = "G. Dirac", TITLE = "On rigid circuit graphs", JOURNAL = "Abhandl. Math. Sem. d. Univ. Hamburg 25", YEAR = "1961", PAGES = "71-76", } @ARTICLE {GRE84, AUTHOR = "J.R. Gilbert; D.J. Rose and A. Edenbrandt", TITLE = "A seperator theorem for chordal graphs", JOURNAL = "SIAM J. Alg. Discr. Meth. Vol 5 No 3", YEAR = "1984", PAGES = "306-313", } @ARTICLE {FG65, AUTHOR = "D.R. Fulkerson and O.A. Gross" , TITLE = "Incidence matrices and interval graphs", JOURNAL = "Pacif. J. Math 15", YEAR = "1965", PAGES = "835-855", } @ARTICLE {Ros70, AUTHOR = "D.J. Rose.", TITLE = " Trainagulated graphs and the elimination process", JOURNAL = "J. Math Anal. Appl. 32", YEAR = "1970", PAGES = "597-609", } @ARTICLE {Shi88, AUTHOR = "Y. Shibata", TITLE = "On the tree representations of chordal graphs", JOURNAL = "J. Graph Th. 12 No. 3", YEAR = "1988", PAGES = "421-428", } @ARTICLE {Lub87, AUTHOR = "A. Lubiw", TITLE = "Doubly lexical orderings of matrices", JOURNAL = "SIAM J. Comput 16. No. 5.", YEAR = "1987", PAGES = "854-879", } @ARTICLE {GH64, AUTHOR = "P.C. Cilmore and A.J. Hoffman", TITLE = "A characterization of comparability graphs and interval graphs", JOURNAL = "Canad. J. Math 16", YEAR = "1964", PAGES = "539-548", } @ARTICLE {Haj57, AUTHOR = "G. Hajos", TITLE = "Uber eine Art Von Graphen", JOURNAL = "Intern. Math. Nachr 11 Problem 65.", YEAR = "1957", } @ARTICLE {Ber60, AUTHOR = "C. Berge", TITLE = "Les problemes de colorations en theorie des graphs", JOURNAL = "Publ. Inst Statist. Univ. Paris 9", YEAR = "1960", PAGES = "123-160", } @ARTICLE {Gav72, AUTHOR = "F. Gavril", TITLE = "Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph", JOURNAL = "SIAM J. Comput 1", YEAR = "1972", PAGES = "180-187", } @ARTICLE {Tuz90, AUTHOR = "Z. Tuza", TITLE = "Covering All cliques of a graph", JOURNAL = "Discrete Mathematics 86", YEAR = "1990", PAGES = "117-126", } @ARTICLE {KDL94, AUTHOR = "D. Kratsh; P. Damaschke, A. Lubiw", TITLE = "Dominating Cliques in chordal graphs", JOURNAL = "Discrete Mathematics 128", YEAR = "1994", PAGES = "269-275", } @ARTICLE {LPHH84, AUTHOR = "R. Laskar; J. Pfaff; S.M. Hedetniemi and S.T. Hedetniemi", TITLE = "On the algorithmic complexity of total domination", JOURNAL = "SIAM J. Algebraic Discrete Meth 5", YEAR = "1984", PAGES = "420-425", } @ARTICLE {AA86, AUTHOR = "M. Aigner and T. Andreae", TITLE = "Vertex sets that meet all maximal cliques of a graph", JOURNAL = "Manuscript", YEAR = "1986", } @ARTICLE {And87, AUTHOR = "T. Andreae", TITLE = "Covering the maximal cliques of a graph with at most half of its vertices", JOURNAL = "Manuscript", YEAR = "1987", } @ARTICLE {CCM86, AUTHOR = "M. Conforti; D.G. Corneil and A.R. Mahjoub", TITLE = "Ki-covers I: Complexity and polytopes", JOURNAL = "Discrete mathematics 58(2)", YEAR = "1986", PAGES = "121-142", } @ARTICLE {CF88, AUTHOR = "D.G. Corneil and J. Fonlupt", TITLE = "The complexity of generalized clique covering", JOURNAL = "Discrete Applied Mathematics 22(2)", YEAR = "1988/1989", PAGES = "109-118", } @ARTICLE {Tar76, AUTHOR = "R.Tarjan", TITLE = "Maximum Cardinality Search and Chordal Graphs", JOURNAL = "Unpublished lecture notes, Standford University", YEAR = "1976", } @ARTICLE {Shi84, AUTHOR = "D.R. Shier", TITLE = "Some aspects of perfect elimination orderings in chordal graphs", JOURNAL = "Discrete Applied Mathematics 7(3)", YEAR = "1984", PAGES = "325-331", } @ARTICLE {Sch84, AUTHOR = "E.R. Scheinerman", TITLE = "Intersection classes and multiple intersection parameters of graphs", JOURNAL = "PhD Thesis Princeton", YEAR = "1984", } @ARTICLE {Wes84, AUTHOR = "D.B. West", TITLE = "Parameters of partial orders: Packing, covering and representation", JOURNAL = "Graphs and order: Proc. of the Conf. at Banff Canada", YEAR = "1984", PAGES = "267-350", } @ARTICLE {And87b, AUTHOR = "T.Andreae", TITLE = "On the interval number of a triangulated graph", JOURNAL = "J. Graph Theory 11", YEAR = "1987", PAGES = "273-280", } @ARTICLE {Sch88, AUTHOR = "E.R. Scheinerman", TITLE = "On the interval number of chordal graphs", JOURNAL = " J. Graph Theory 12(3)", YEAR = "1988", PAGES = "311-316", } @ARTICLE {Dah94, AUTHOR = "E. Dahlhaus", TITLE = "A parallel algorithm for computing Steiner trees in strongly chordal graphs", JOURNAL = "Discrete Applied Mathematics 51", YEAR = "1994", PAGES = "47-61", } @ARTICLE {WFP85, AUTHOR = "K. White; M. Farber and W. Pulleyblank", TITLE = "Steriner Trees, connected domination and strongly chordal graphs", JOURNAL = "Networks 15", YEAR = "1985", PAGES = "109-124", } @ARTICLE {AAM86, AUTHOR = "G. Ausiello; A. D'Atri and M. Moscarini", TITLE = "Chordality properties on graphs and minimal conceptual connections in semantic data models", JOURNAL = "J. Comput Systems Sci 33", YEAR = "1986", PAGES = "179-202", } @ARTICLE {Dah91, AUTHOR = "E. Dahlhaus", TITLE = "Chordale Graphen im hesonderen Hinbliek auf Parallele Agorithmen", JOURNAL = "Habilitaiton Thesis University of Bonn", YEAR = "1991", } @ARTICLE {HL88, AUTHOR = "C.W. Ho and R.C.T. Lee", TITLE = "Efficient parallel algorithms for finding maximal cliques, clique tress and minimum coloring on a chordal graph", JOURNAL = "Information Processing Letters 28", YEAR = "1988", PAGES = "301-309", } @ARTICLE {Ho89, AUTHOR = "C.W. Ho", TITLE = "Counting clique trees and computing perfect elimination schemes in parallel", JOURNAL = "Information Processing Letters 31(2)", YEAR = "1989", PAGES = "61-68", } @ARTICLE {NNS87, AUTHOR = "J. Naor; M. Naor and A.A. Schaffer", TITLE = "Fast parallel algorithms for chordal graphs", JOURNAL = "Proc 19th Annual ACM Symp. on Theory of Computing", YEAR = "1987", PAGES = "355-364", } @ARTICLE {Ede87, AUTHOR = "A. Edenbrandt", TITLE = "Chordal graph recognition is in NC", JOURNAL = "Information processing letters 24(4)", YEAR = "1987", PAGES = "239-241", } % % Overview % @article(Hour62, author= "A. Ghouila-Houri", title= "Characterization des graphes non orient\'{e}s dont on peut orienter les arr\^{e}tes de mani\`{e}re \`{a} obtenir le graph d'une relation d'ordre", journal= "C.R. Acad. Sci. Paris", annote= "One of the first articles about characterization of comparability graphs.", vol= 254, year= 1962, pages= "1370-1371" ) @article(GiHo64, author= "P.C. Gilmore and A.J.Hoffman", title= "A characterization of comparability graphs and of interval graphs", journal= "Canadian Journal of Mathematics", annote= "One of the first articles in which characterization of comparability graphs is studied.", volume= 16, year= 1964, pages= "539-548" ) @article(Gall67, author= "Tibor Gallai", title= "Transitiv orientierbare graphen", journal= "Acta Math. Acad. Sci. Hungar.", annote= "Contains many results on the structure of comparability graphs.", volume= 18, year= 1967, pages= "25-66" ) @Book(Golu80, author = "M.C. Golumbic", title = "Algorithmic graph theory and perfect graphs", publisher = "Academic Press", annote= "Good overview of perfect graphs. One chapter of the book is entirely devoted to comparability graphs.", year = "1980", address = "New York, NY" ) @InCollection(Kell84, author = "David Kelly", title = "Comparability Graphs", booktitle= "Graphs and Order", editor= "Ivan Rival", pages= "3--40", publisher = "D. Reidel Publishing Company", year = "1985", address = "", annote= "Many important results about comparability graphs are discusses, especially characterization issues." ) @InCollection(Mohr84, author = "R.H. Mohring", title = "Algorithmic aspects of comparability graphs and interval graphs", booktitle= "Graphs and Order", editor= "Ivan Rival", pages= "41--101", publisher = "D. Reidel Publishing Company", year = "1985", address = "", annote= "The first part of the paper surveys various algorithmic methods developed for comparability graphs. In the second part, algorithmic methods are given for recognition of interval graphs and for solving combinatorial optimization problems for these graphs." ) % % Transitive orientation, modular decomposition and recognition % @unpublished(McSp95, author= "Ross M. McConnell and Jeremy P. Spinrad", title= "Modular decomposition and transitive orientation", annote= "A linear, $O(n+m)$, algorithm is given for modular decomposition and transitive orientation of graphs. This gives linear time bounds for recognizing permutation graphs, maximum clique and minimum vertex coloring on comparability graphs, and other combinatorial problems on comparability graphs and their complements.", year= 1995, note= "Unpublished" ) @unpublished(CoHa95, author= "Alain Cournier and Michel Habib", title= "A linear algorithm to build Modular Decomposition Trees", annote= "A linear algorithm for modular decomposition is presented. New structural properties of prime graphs and modules, and a cograph recognition algorithm are used in the presented algorithm to obtain the linear bounds.", year= 1995, note= "Unpublished" ) @article(McCo95, author= "Ross M. McConnell", title= "An $O(n^{2})$ incremental algorithm for modular decomposition of graphs and 2-structures", journal= "Algorithmica", annote= "An $O(n^{2})$ algorithm is given for computing the modular decomposition for 2-structures. The modular decomposition is of interest to the study of relational systems.", volume= 14, year= 1995, pages= "229--248" ) @article(Spin92, author= "Jeremy P. Spinrad", title= "P4-trees and substitution decomposition", journal= "Discrete Applied Mathematics", annote= "The paper introduces a new data structure, $P_{4}$-trees, which is then used as part of an algorithm to find the substitution decomposition of a graph in $O(m\alpha(m,n))$ time.", volume= 39, year= 1992, pages= "263-291" ) @article(MuSp89, author= "John H. Muller and Jeremy Spinrad", title= "Incremental Modular Decomposition", journal= "Journal of the {ACM}", annote= "An $O(n^{2})$ algorithm for modular decomposition is given. The new algorithm works by inserting each vertex successively into the decomposition tree, using $O(n)$ time to insert each vertex.", volume= 36, year= 1989, pages= "1--19" ) @article(Spin85, author= "Jeremy P. Spinrad", title= "On comparability and permutation graphs", journal= "SIAM Journal of Computing", annote= "An algorithm is presented for orienting a comparability graph transitively in $O(n^{2})$.", volume= 14, year= 1985, pages= "658--670" ) @article(PLE71, author= "Amir Pnueli and Abraham Lempel and Shimon Even", title= "Transitive orientation of graphs and identification of permutation graphs", journal= "Canadian Journal of Mathematics", annote= "An iterative procedure for testing transitive orientability of a graph is described. It's also shown that a graph $G$ is a permutation graph iff both $G$ and its complement are transitively orientable(i.e. comparability graphs).", volume= 23, year= 1971, pages= "160--175") @article(EPL72, author= "Shimon Even and Amir Pnueli and Abraham Lempel", title= "Permutation graphs and Transitive Graphs", journal= "Journal of the Association for Computing Machinery", annote= "A structural relationship is established between permutation graphs and transitive (comparability) graphs and an algorithm for determining whether a given graph is permutation graph is given. Furthermore, algorithms for finding a maximum size clique and a minimum coloring of transitive graphs are presented.", volume= 19, year= 1972, pages= "400-410") @article(Golu77a, author= "M.C. Golumbic", title= "Comparability graphs and a new matroid", journal= "Journal of Combinatorial Theory", annote= "", volume= 22, year= 1977, pages= "68-90" ) @article(Golu77b, author= "M.C. Golumbic", title= "The complexity of comparability graph recognition and coloring", journal= "Computing", annote= "An algorithm is presented which assigns a transitive orientation to a comparability graph in $O(\delta m)$ time. This makes finding the maximum clique and the minimum vertex coloring problem solvable in $O(\delta m)$ time for comparability graphs.", volume= 18, year= 1977, pages= "199-208" ) @Book(GaJo79, author = "Michael R. Garey and David S. Johnson", title = "Computers and Intractability", publisher = "W.H. Freeman and Company", year = "1979", address = "New York, NY" ) @article(CaKo92, author= "Yang Cai and M.C. Kong", title= "Generation of All Maximal Cliques and Related Problems for Certain Perfect Graphs", journal= "Congressus Numerantium", annote= "A fast algorithm for generation all maximal cliques/independent sets for various perfect graphs is presented. In particular, comparability, cocomparability and permutation graphs are considered.", volume= 90, year= 1992, pages= "33-55" ) @article(CoPe84, author= "D.G. Corneil and Y. Pearl", title= "Clustering and domination in perfect graphs", journal= "Discrete Applied Mathematics", annote= "The $k$-cluster and the $k$-domination problems are known to be {NP}-complete for graphs in general. In this paper the complexity of these problems on various subclasses of perfect graphs are investigated.", volume= 9, year= 1984, pages= "27-40" ) @TechReport(PLH83, author = "J. Pfaff and R. Lasker and S.T. Hedetniemi", title = "{NP}-completeness of connected and total domination and irredundance for bipartite graphs", institution = "Clemson University", year = "1983", number = "428" ) @TechReport(Dewd81, author = "A.K. Dewdnay", title = "Fast Turing reductions between problems in {NP}", institution = "University of Western Ontario", year = "1981", number = "71" ) @InProceedings(BoLu75, author= "K.S. Booth and G.S. Lueker", title= "Linear algorithms to recognize interval graphs and test for consecutive ones property", booktitle= "Proceedings of the Seventh Annual {ACM} Symposium on Theory of Computing", annote= "A linear algorithm for recognizing interval graphs and finding various properties for them is given. It's shown that it can be determined in linear time if two interval graphs are isomorphic. It's furthermore shown that graph isomorphism for comparability graphs is as hard as for general graphs.", year= 1975, pages= "255--265" ) @article(Kris76, author= "M.S. Krishnamoorthy", title= "An {NP}-hard problem in bipartite graphs", journal= "{SIGACT} News", annote= "Checking for Hamiltonian circuit in bipartite graphs is shown to be {NP}-hard.", volume= 7, year= 1976, pages= "26" ) @TechReport(DeSt91, author = "J. Deogun and G.Steiner", title = "Polynomial algorithms for Hamiltonian cycle in cocomparability graphs", institution = "University of Nebraska", year = "1991", number = "145" ) @article(KrSt93, author= "D. Kratsch and L. Steward", title= "Domination on co-comparability graphs", journal= "SIAM Journal on Discrete Mathematics", annote= "", volume= 6, year= 1993, pages= "400-417" ) %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} ) @article(BFR71, author= "K.A. Baker and P.C. Fishburn and F.S. Roberts", title= "Partial orders of dimension 2", journal= "Networks", volume= 2, year= 1971, pages= "11-28") @article(CSt90, author= "C. J. Colbourn and L. Stewart", title= "Permutation graphs: Connected domination and Steiner trees", journal= "Discrete Mathematics", volume= 86, year= 1990, pages= "179-189") @article(Ste86, author= "L. Stewart", title= "Permutation graph structure", journal= "Congressus Numerantium", volume= 54, year= 1986, pages= "87-100") @article(BHW85, author= "C. Benzaken and P.L. Hammer and D. de Werr", title= "Threshold characterization of graphs with Dilworth number two", journal= "J. Graph Th.", volume= 9, year= 1985, pages= "245-267") @article(BKr85, author= "A. Brandstadt and D. Kratsch", title= "On dominating problems for permutation and other graphs", journal= "Forschungsergebnisse Friedriech-Schiller-Univeritat Jena", volume= 41, year= 1985) @article(Col81, author= "C.J. Colbourn", title= "On testing isomorphism of permutation graphs", journal= "Networks", volume= 11, year= 1981, pages= "13-21") @article(CKS85, author= "C.J. Colbourn and J.M. Keil and L.K. Stewart", title= "Finding minimum dominating cycles in permutation graphs", journal= "Oper. Res. Lett.", volume= 4, year= 1985, pages= "13-17") @techreport(CH73, author= "V. Chvatal and P.L. Hammer", title= "Set-packing and threshold graphs", institution= "Univ. Waterloo", year= 1973, number= "CORR 13-21") @article(CK87, author= "D.C. Corneil and P.A. Kamula", title= "Extensions of permutation and interval graphs", journal= "Proc. of 18th SE Conf.", year= 1987) @article(Dam89, author= "P. Damaschke", title= "Forbidden ordered subgraphs", journal= "manuscript", year= 1989) @article(DGP88, author= "I. Dagan and M.C. Golumbic and R.Y. Pinter", title= "Trapezoid graphs and their coloring", journal= "D.A.M.", volume= 21, year= 1988, pages= "35-46") @article(DM41, author= "B. Dushnik and E.W. Miller", title= "Partially ordered sets.", journal= "Amer. J. Math.", volume= 63, year= 1941, pages= "600-610") @incollection(EI71, author= "S. Even and A. Itai", title= "Queues, stacks and graphs", booktitle= "Theory of Machines and Computations", pages= "71-86", publisher= "Acad. Press. N.Y.", year= 1971) @article(ELP72, author= "S. Even and A. Lempel and A. Pnueli", title= "Permutation graphs and transitive graphs", journal= "J. ACM", volume= 19, year= 1972, pages= "400-410") @article(ESz35, author= "P. Erdos and G. Szekeres", title= "A combinatorial problem in geometry", journal= "Compositio Math.", volume= 2, year= 1935, pages= "463-470.") @article(FK85, author= "M. Farber and J.M. Keil", title= "Domination in permutation graphs", journal= "J. Algorithms", volume= 6, year= 1985, pages= "309-321") @unpublished(GAc77, author= "M.K. Gill and B.D. Acharya", title= "A new characterization of permutation graphs", note= "unpublished", year= 1977) @article(GHo64, author= "P.C. Gilmore and A.J. Hoffman", title= "A characterization of comparability graphs and of interval graphs", journal= "Canad. J. Math", volume= 16, year= 1964, pages= "539-548") @article(GM82, author= "M.C. Golumbic and C.L. Monma", title= "A generalization of interval graphs with tolerances", journal= "Proc. of 13th SE Conf.", volume= 35, year= 1982, pages= "321-331") @article(Gol77, author= "M.C. Golumbic", title= "The complexity of comparability graphs recognition and coloring", journal= "Comput.", volume= 18, year= 1977, pages= "199-208") @book(Gol80, author= "M.C. Golumbic", title= "Algorithmic Graph Theory and Perfect Graphs", publisher= "Academic Press", year= 1980) @article(PLE71, author= "A. Pnueli and A. Lempel and S. Even", title= "Transitive orientation of graphs and identification of permutation graphs", journal= "Canad. J. of Math.", volume= 23, year= 1971, pages= "160-165") @techreport(RU84, author= "D. Rotem and J. Urrutia", title= "Circular permutation graphs", institution= "Univ. Waterloo", year= 1984) @article(SBS87, author= "J.P. Spinrad and A. Brandstadt and L.K. Stewart.", title= "Bipartite permutation graphs", journal= "D. A. M.", volume= 18, year= 1987, pages= "279-292") @phdthesis(Spi82, author= "J.P. Spinrad", title= "Two Dimensional Partial Orders", school= "Dept. of EECS, Princeton, N.J.", year= 1982) @article(Spi85, author= "J.P. Spinrad", title= "On comparability and permutation graphs", journal= "SIAM J. Comput.", volume= 14, year= 1985, pages= "658-670") @article(SSt87, author= "G. Steiner and L.K. Stewart", title= "A linear time algorithm to find the jump number of two dimensional bipartite partial orders", journal= "Order", volume= 3, year= 1987, pages= "359-367") @phdthesis(Ste85, author= "L.K. Stewart", title= "Permutation graph structure and algorithms", school= "Univ. of Toronto, Dept. of Computer Science", year= 1985) @article(PS85, author= "B. Piazza and S. Stueckle", title= "On the cut frequency vector of permutation graphs", journal= "Congr. Numer.", volume= 49, year= 1985, pages= "143-145") @article(PPS82, author= "G. Pica and T. Pisanski and J. Shawe-Taylor", title= "The permutation girth of a graph", journal= "Atti Sem. Mat. Fis. Univ. Modena", volume= 31, year= 1982, pages= "297-301") @article(Pia84, author= "B. Piazza", title= "On Hamiltonian cycles in cycle permutation graphs", journal= "Congr. Numer.", volume= 45, year= 1984, pages= "83-90") @article(SR84, author= "S. Stueckle and R.D. Ringeisen", title= "Generalized Petersen graphs which are cycle permutation graphs", journal= "Journal of Combinatorial Theory. Series B.", volume= 37, number= 2, year= 1984, pages= "142-150") @article(Rin84, author= "R.D. Ringeisen", title= "On cycle permutation graphs", journal= "Discrete Mathematics", volume= 51, year= 1984, number= 3, pages= "265-275") @article(PS82, author= "T. Pisanski and J. Shawe-Taylor", title= "Cycle permutation graphs with large girth", journal= "Glas. Mat. Ser.", volume= 17, number= 2, year= 1982, pages= "233-236") @article(RU82, author= "D. Rotem and J. Urrutia", title= "Circular permutation graphs", journal= "Networks", volume= 12, number= 4, year= 1982, pages= "429-437") @article(RU81, author= "D. Rotem and J. Urrutia", title= "Search for minimal trivalent cycle permutation graphs with grith nine", journal= "Discrete Mathematics", volume= 36, number= 1, year= 1981, pages= "113-115") @article(Pia90, author= "B. Piazza", title= "Hamiltonian-type properties of permutation graphs", journal= "Congr. Numer.", volume= 72, year= 1990, pages= "5-8") @article(AK89, author= "M. J. Atallah and R.S. Kosaraju", title= "An efficient algorithm for maxdominance, with applications", journal= "Algorithmica", volume= 4, number= 2, year= 1989, pages= "221-236") @article(BSS87, author= "A. Brandstadt and J. Spinrad and L.K. Stewart.", title= "Bipartite permuatation graphs are bipartite tolerance graphs", journal= "Congr. Numer.", volume= 58, year= 1987, pages= "165-174") @article(AMU88, author= "M. J. Atallah and G.K. Manacher and J. Urrutia", title= "Finding a minimum independent dominating set in a permutation graph", journal= "D. A. M.", volume= 21, number= 3, year= 1988, pages= "177-183") @article(IZ94, author= "O.H. Ibarra and Q. Zheng", title= "Some efficient algorithms for permutation graphs", journal= "J. of Algorithms", volume= 16, number= 3, year= 1994, pages= "453-469") @article(Bou94, author= "N. Bouaza", title= "Split permutation graphs", journal= "C. R. Acad. Sci. Paris Ser. I Math.", volume= 318, number= 11, year= 1994, pages= "971-977") @article(DKKM94, author= "J.S. Deogun and T. Kloks and D. Kratsch and H. Muller", title= "On vertex ranking for permutation graphs and other graphs", journal= "Lecter notes in Comput. Sci.", volume= 775, year= 1994, pages= "747-758") @article(YC94, author= "C.W. Yu and G.H. Chen", title= "A theorem on permutation graphs with applications", journal= "Inform. Sci.", volume= 77, number= 3, year= 1994, pages= "179-193") @article(RLDL94, author= "C. Rhee and D.Y. Liang and S.K. Dhall and S. Lakshmivarahan", title= "Efficient algorithm for finding depth-first search and breadth-first search trees in permutation graphs", journal= "Inform. Process. Lett.", volume= 49, number= 1, year= 1994, pages= "45-50") @article(BKK93, author= "H. Bodlaender and T. Kloks and D. Kratsch", title= "Treewidth and pathwidth of permutation graphs", journal= "Lecture Notes in Comput. Sci.", volume= 700, year= 1993, pages= "114-125") @article(LS91, author= "D.T. Lee and M. Sarrafzadeh", title= "Maximum independent set of a permutation graph with $K$ tracks", journal= "Internat. J. Comput. Geom. Appl.", volume= 3, number= 3, year= 1993, pages= "291-304") @article(TH93, author= "K. Tsai and W. Hsu", title= "Fast algorithms for the dominating set problem on permutation graphs", journal= "Algorithmica", volume= 9, number= 6, year= 1993, pages= "601-614") @article(LS92, author= "R.D. Lou and M. Sarrafzadeh", title= "Circular permutation graph family with applications", journal= "D. A. M.", volume= 40, number= 3, year= 1992, pages= "433-457") @unpublished(McCS95, author= "Ross M. McConnell and Jeremy P. Spinrad", title= "Modular decomposition and transitive orientation", year= 1995, note= "Unpublished") @article(CK92, author= "Y. Cai and M.C. Kong", title= "Generating all maximal cliques and related problems for certain perfect graphs", journal= "Congr. Numer.", volume= 90, year= 1992, pages= "33-55")