×

zbMATH — the first resource for mathematics

Mixed searching and proper-path-width. (English) Zbl 0873.68148
Summary: This paper considers a mixed search game, which is a natural generalization of edge-search and node-search games extensively studied so far. We establish a relationship between the mixed-search number of a graph \(G\) and the proper-path-width of \(G\) introduced by the authors in a previous paper. We also prove complexity results.

MSC:
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnborg, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. algebraic discrete methods, 8, 277-284, (1987) · Zbl 0611.05022
[2] Bienstock, D.; Seymour, P., Monotonicity in graph searching, J. algorithms, 12, 239-245, (1991) · Zbl 0760.05081
[3] Bodlaender, H.L., Improved self-reduction algorithms for graphs with bounded treewidth, (), 232-244 · Zbl 0768.68033
[4] Bodlaender, H.L.; Kloks, T., Better algorithm for the pathwidth and treewidth of graphs, (), 544-555 · Zbl 0764.68108
[5] Breisch, R.L., An intuitive approach to speleotopology, (), 72-78
[6] Johnson, D.S., The NP-completeness column: an ongoing guide, J. algorithms, 8, 285-303, (1987) · Zbl 0626.68039
[7] Kirousis, L.M.; Papadimitriou, C.H., Interval graphs and searching, Discrete math., 55, 181-184, (1985) · Zbl 0566.05056
[8] Kirousis, L.M.; Papadimitriou, C.H., Searching and pebbling, Theoret. comput. sci., 47, 205-218, (1986) · Zbl 0616.68064
[9] LaPaugh, A.S., Recontamination does not help to search a graph, J. ACM, 40, 224-245, (1993) · Zbl 0768.68048
[10] Megiddo, M.; Hakimi, S.L.; Garey, M.R.; Johnson, D.S.; Papadimitriou, C.H., The complexity of searching a graph, J. ACM, 35, 18-44, (1988) · Zbl 0637.68081
[11] Möhring, R.H., Graph problems related to gate matrix layout and PLA folding, (), 17-51, computing suppl · Zbl 0699.68072
[12] Parsons, T.D., Pursuit-evasion in a graph, (), 426-441 · Zbl 0379.05026
[13] Robertson, N.; Seymour, P.D., Graph minors. I. excluding a forest, J. combin. theory ser., B35, 39-61, (1983) · Zbl 0521.05062
[14] Robertson, N.; Seymour, P.D., Graph minors. XIII. the disjoint paths problem, (1986), preprint · Zbl 0823.05038
[15] Robertson, N.; Seymour, P.D., Graph minors. XVI. Wagner’s conjecture, (1987), preprint · Zbl 1061.05088
[16] Scheffer, P., A linear algorithm for the pathwidth of trees, (), 613-620
[17] Shinoda, S., On some problems of graphs — including Kajitani’s conjecture and its solution, (), 414-418, (in Japanese)
[18] Takahashi, A.; Ueno, S.; Kajitani, Y., Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Discrete math., 127, 293-304, (1994) · Zbl 0795.05123
[19] Takahashi, A.; Ueno, S.; Kajitani, Y., Mixed-searching and proper-path-width, () · Zbl 0873.68148
[20] Takahashi, A.; Ueno, S.; Kajitani, Y., Mixed-searching and proper-path-width, (), 61-71
[21] Takahashi, A.; Ueno, S.; Kajitani, Y., On the proper-path-decomposition of trees, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.