Graph searching on chordal graphs

1. S. ARNBORG, D.G. CORNEIL, and A. PROSKUROWSKI, Complexity of finding embeddings in a k-tree, SIAM J. Alg. Disc. Meth., 8(1987), pp. 277–284.

   Google Scholar 

2. H.L. BODLAENDER, T. KLOKS, and D. KRATSCH, Treewidth and pathwidth of permutation graphs, 20th ICALP, LNCS 700(1993), pp. 114–125.

   Google Scholar 

3. H.L. BODLAENDER and R.H. MOHRING, The pathwidth and treewidth of cographs, SIAM J. Disc. Math., 6(1993), pp. 181–188.

   Article  Google Scholar 

4. D. BIENSTOCK and P. SEYMOUR, Monotonicity in graph searching, J. Algorithms, 12(1991), pp. 239–245.

   Article  Google Scholar 

5. F. GAVRIL, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Comb. Theory Ser. B, 16(1974), pp.47–56.

   Article  Google Scholar 

6. J. GUSTEDT, On the pathwidth of chordal graphs, Discr. Appl. Math. 45(1993), pp. 233–248.

   Article  Google Scholar 

7. N.G. KINNERSLEY, The vertex separation number of a graph equals its path-width, Inform. Process. Letter, 42(1992), pp. 345–350.

   Article  Google Scholar 

8. T. KLOKS, Treewidth, Ph.D. Thesis, Utrecht University, The Netherlands, 1993.

   Google Scholar 

9. L.M. KIROUSIS and C.H. PAPADIMITRIOU, Interval graph and searching, Disc. Math. 55(1985), pp. 181–184.

   Article  Google Scholar 

10. L.M. KIROUSIS and C.H. PAPADIMITRIOU, Searching and pebbling, Theoretical Comp. Scie. 47(1986), pp. 205–218.

    Google Scholar 

11. A. KORNAI and Z. TUZA, Narrowness, pathwidth, and their application in natural language processing, Disc. Appl. Math., 36(1992), pp. 87–92.

    Article  Google Scholar 

12. A.S. LAPAUGH, Recontamination does not help to search a graph, J. of the Assoc. Comput. Mach., 40(1993), pp. 224–245.

    Google Scholar 

13. N. MEGIDDO, S.L. HAKIMI, M.R. GAREY, D.S. JOHNSON, and C.H. PAPADIMITRIOU, The complexity of searching a graph, J. of the Assoc. Comput. Mach., 35(1988), pp. 18–44.

    Google Scholar 

14. R.H. MOHRING, Graph problems related to gate matrix layout and PLA folding, in: G. TINNHOFER et al., eds., Computational Graph Theory (Springer, Wien, 1990), pp. 17–32.

    Google Scholar 

15. B. MONIEN and I.H. SUDBOROUGH, Min cut is NP — complete for edge weighted trees, Theoretical Comp. Scie. 58(1988), pp. 209–229.

    Google Scholar 

16. T.D. PARSONS, Pursuit-evasion in a graph, in Y. ALAVI and D.R. LICK, eds., Theory and applications of graphs, Springer-Verlag, New York, 1976, pp. 426–441.

    Google Scholar 

17. N. ROBERTSON and P.D. SEYMOUR, Graph minors I. Excluding a forest, J. Comb. Theory Ser. B, 35(1983), pp. 39–61.

    Google Scholar 

18. P. SCHEFFLER, A linear algorithm for the pathwidth of trees, in: R. BODENDIEK and R. HENN, eds., Topics in Combinatorics and Graph Theory (Physica-Verlag, Heidelberg, 1990), pp. 613–620.

    Google Scholar 

Download references