×

Edge search number of cographs in linear time. (English) Zbl 1248.05200

Deng, Xiaotie (ed.) et al., Frontiers in algorithmics. Third international workshop, FAW 2009, Hefei, China, June 20–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02269-2/pbk). Lecture Notes in Computer Science 5598, 16-26 (2009).
Summary: We give a linear-time algorithm for computing the edge search number of cographs, thereby proving that this problem can be solved in polynomial time on this graph class. With our result, the knowledge on graph searching of cographs is now complete: node, mixed, and edge search numbers of cographs can all be computed efficiently. Furthermore, we are one step closer to computing the edge search number of permutation graphs.
For the entire collection see [Zbl 1166.68003].

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alpern, S., Gal, S.: The theory of search games and rendezvous. International Series in Operations Research & Management Science, vol. 55. Kluwer Academic Publishers, Boston (2003) · Zbl 1034.91017
[2] Alspach, B., Dyer, D., Hanson, D., Yang, B.: Lower Bounds on Edge Searching. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol. 4614, pp. 516–527. Springer, Heidelberg (2007) · Zbl 1176.91017 · doi:10.1007/978-3-540-74450-4_46
[3] Bienstock, D.: Graph searching, path-width, tree-width and related problems (a survey), DIMACS Ser. Discrete Mathematics and Theoretical Computer Science 5, 33–49 (1991) · Zbl 0777.05090
[4] Bienstock, D., Seymour, P.: Monotonicity in graph searching. J. Algorithms 12, 239–245 (1991) · Zbl 0760.05081 · doi:10.1016/0196-6774(91)90003-H
[5] Bodlaender, H.L., Kloks, T., Kratsch, D.: Treewidth and pathwidth of permutation graphs. SIAM J. Disc. Math. 8, 606–616 (1995) · Zbl 0840.05087 · doi:10.1137/S089548019223992X
[6] Bodlaender, H.L., Kloks, T., Kratsch, D., Möhring, R.H.: Treewidth and Minimum Fill-in on d-Trapezoid Graphs. J. Graph Algorithms Appl. 2 (1998) · Zbl 0905.68101 · doi:10.7155/jgaa.00008
[7] Bodlaender, H.L., Möhring, R.H.: The pathwidth and treewidth of cographs. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol. 447, pp. 301–310. Springer, Heidelberg (1990) · Zbl 0773.05091 · doi:10.1007/3-540-52846-6_99
[8] Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comp. Syst. Sc. 13, 335–379 (1976) · Zbl 0367.68034 · doi:10.1016/S0022-0000(76)80045-1
[9] Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics (1999) · Zbl 0919.05001 · doi:10.1137/1.9780898719796
[10] Chou, H., Ko, M., Ho, C., Chen, G.: Node-searching problem on block graphs. Disc. Appl. Math. 156, 55–75 (2008) · Zbl 1131.68043 · doi:10.1016/j.dam.2007.08.007
[11] Corneil, D.G., Lerchs, H., Stewart Burlingham, L.: Complement reducible graphs. Annals Discrete Math. 1, 145–162 (1981) · Zbl 0463.05057
[12] Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM Journal on Computing 14, 926–934 (1985) · Zbl 0575.68065 · doi:10.1137/0214065
[13] Ellis, J., Markov, M.: Computing the vertex separation of unicyclic graphs, Inf. Comput. 192, pp. 123–161 (2004) · Zbl 1069.68077 · doi:10.1016/j.ic.2004.03.005
[14] Fomin, F.V., Fraigniaud, P., Nisse, N.: Nondeterministic Graph Searching: From Pathwidth to Treewidth. Algorithmica (2008) · Zbl 1172.68046
[15] Fomin, F., Heggernes, P., Mihai, R.: Mixed search number and linear-width of interval and split graphs. In: Brandstädt, A., Kratsch, D., Müller, H. (eds.) WG 2007. LNCS, vol. 4769, pp. 304–315. Springer, Heidelberg (2007) · Zbl 1141.68526 · doi:10.1007/978-3-540-74839-7_29
[16] Fomin, F., Thilikos, D.: An annotated bibliography on guaranteed graph searching. Theor. Comput. Sci. 399, 236–245 (2008) · Zbl 1160.68007
[17] Golovach, P.A.: Extremal search problems on graphs, Ph.D Thesis, Leningrad (1990) · Zbl 0713.90038
[18] Golovach, P.A., Petrov, N.N.: Some generalizations of the problem on the search number of a graph. Vestn. St. Petersbg. Univ., Math. 28(3), 18–22 (1995); translation from Vestn. St-Peterbg. Univ., Ser. I, Mat. Mekh. Astron., 3, pp. 21–27 (1995) · Zbl 0883.90149
[19] Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, vol. 57. North-Holland, Amsterdam (2004) · Zbl 1050.05002
[20] Gustedt, J.: On the pathwidth of chordal graphs. Disc. Appl. Math. 45, 233–248 (1993) · Zbl 0798.68134 · doi:10.1016/0166-218X(93)90012-D
[21] Habib, M., Paul, C.: A simple linear time algorithm for cograph recognition. Discrete Applied Mathematics 145, 183–197 (2005) · Zbl 1055.05107 · doi:10.1016/j.dam.2004.01.011
[22] Heggernes, P., Mihai, R.: Mixed search number of permutation graphs. In: Preparata, F.P., Wu, X., Yin, J. (eds.) FAW 2008. LNCS, vol. 5059, pp. 196–207. Springer, Heidelberg (2008) · Zbl 1143.68588 · doi:10.1007/978-3-540-69311-6_22
[23] Kirousis, L.M., Papadimitriou, C.H.: Interval graphs and searching. Disc. Math. 55, 181–184 (1985) · Zbl 0566.05056 · doi:10.1016/0012-365X(85)90046-9
[24] Kirousis, M., Papadimitriou, C.H.: Searching and pebbling. Theor. Comput. Sci. 47, 205–218 (1986) · Zbl 0616.68064 · doi:10.1016/0304-3975(86)90146-5
[25] Kloks, T., Kratsch, D., Spinrad, J.: On treewidth and minimum fill-in of asteroidal triple-free graphs. Theor. Comp. Sc. 175, 309–335 (1997) · Zbl 0903.68139 · doi:10.1016/S0304-3975(96)00206-X
[26] LaPaugh, A.S.: Recontamination does not help to search a graph. J. ACM 40, 224–245 (1993) · Zbl 0768.68048 · doi:10.1145/151261.151263
[27] Mazoit, F., Nisse, N.: Monotonicity of non-deterministic graph searching. Theor. Comput. Sci. 3, 399, 169–178 (2008) · Zbl 1146.68060 · doi:10.1016/j.tcs.2008.02.036
[28] Megiddo, N., 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 · doi:10.1145/42267.42268
[29] Meister, D.: Computing treewidth and minimum fill-in for permutation graphs in linear time. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 91–102. Springer, Heidelberg (2005) · Zbl 1171.05431 · doi:10.1007/11604686_9
[30] Parsons, T.: Pursuit-evasion in a graph. In: Theory and Applications of Graphs. Springer, Heidelberg (1976) · Zbl 0379.05026
[31] Peng, S.-L., Ko, M.-T., Ho, C.-W., Hsu, T.-s., Tang, C.Y.: Graph searching on some subclasses of chordal graphs. Algorithmica 27, 395–426 (2000) · Zbl 0955.05074 · doi:10.1007/s004530010026
[32] Peng, S.-L., Ho, C.-W., Hsu, T.-s., Ko, M.-T., Tang, C.Y.: Edge and node searching problems on trees. Theor. Comput. Sci. 240, 429–446 (2000) · Zbl 0945.68143 · doi:10.1016/S0304-3975(99)00241-8
[33] Peng, S.-L., Yang, Y.-C.: On the treewidth and pathwidth of biconvex bipartite graphs. In: Cai, J.-Y., Cooper, S.B., Zhu, H. (eds.) TAMC 2007. LNCS, vol. 4484, pp. 244–255. Springer, Heidelberg (2007) · Zbl 1198.05144 · doi:10.1007/978-3-540-72504-6_22
[34] Petrov, N.N.: A problem of pursuit in the absence of information on the pursued. Differentsialnye Uravneniya 18, 1345–1352, 1468 (1982)
[35] Skodinis, K.: Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time. J. Algorithms 47, 40–59 (2003) · Zbl 1053.68072 · doi:10.1016/S0196-6774(02)00225-0
[36] Suchan, K., Todinca, I.: Pathwidth of circular-arc graphs. In: Brandstädt, A., Kratsch, D., Müller, H. (eds.) WG 2007. LNCS, vol. 4769, pp. 258–269. Springer, Heidelberg (2007) · Zbl 1141.68549 · doi:10.1007/978-3-540-74839-7_25
[37] Takahashi, A., Ueno, S., Kajitani, Y.: Mixed searching and proper-path-width. Theor. Comput. Sci. 137, 253–268 (1995) · Zbl 0873.68148 · doi:10.1016/0304-3975(94)00160-K
[38] Yang, B., Zhang, R., Cao, Y.: Searching cycle-disjoint graphs. In: Dress, A.W.M., Xu, Y., Zhu, B. (eds.) COCOA. LNCS, vol. 4616, pp. 32–43. Springer, Heidelberg (2007) · Zbl 1175.68305 · doi:10.1007/978-3-540-73556-4_6
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.