{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:08Z","timestamp":1740109328190,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2022,5,21]],"date-time":"2022-05-21T00:00:00Z","timestamp":1653091200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,5,21]],"date-time":"2022-05-21T00:00:00Z","timestamp":1653091200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,9]]},"DOI":"10.1007\/s00453-022-00981-5","type":"journal-article","created":{"date-parts":[[2022,5,21]],"date-time":"2022-05-21T16:02:44Z","timestamp":1653148964000},"page":"2642-2666","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Graph Searches and Their End Vertices"],"prefix":"10.1007","volume":"84","author":[{"given":"Guozhen","family":"Rong","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6927-438X","authenticated-orcid":false,"given":"Yixin","family":"Cao","sequence":"additional","affiliation":[]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Zhifeng","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,21]]},"reference":[{"key":"981_CR1","doi-asserted-by":"publisher","unstructured":"Beisegel, J., Denkert, C., K\u00f6hler, E., Krnc, M., Pivac, N., Scheffler, R., Strehler, M.: On the end-vertex problem of graph searches. Discrete Math. Theor. Comput. Sci. 21(1), (2019). https:\/\/doi.org\/10.23638\/DMTCS-21-1-13","DOI":"10.23638\/DMTCS-21-1-13"},{"issue":"4","key":"981_CR2","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1137\/0210059","volume":"10","author":"PA Bernstein","year":"1981","unstructured":"Bernstein, P.A., Goodman, N.: Power of natural semijoins. SIAM J. Comput. 10(4), 751\u2013771 (1981). https:\/\/doi.org\/10.1137\/0210059","journal-title":"SIAM J. Comput."},{"issue":"2","key":"981_CR3","doi-asserted-by":"publisher","first-page":"100","DOI":"10.3390\/a3020100","volume":"3","author":"A Berry","year":"2010","unstructured":"Berry, A., Blair, J.R.S., Bordat, J.P., Simonet, G.: Graph extremities defined by search algorithms. Algorithms 3(2), 100\u2013124 (2010). https:\/\/doi.org\/10.3390\/a3020100","journal-title":"Algorithms"},{"issue":"1\u20133","key":"981_CR4","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0166-218X(98)00005-5","volume":"84","author":"A Berry","year":"1998","unstructured":"Berry, A.: Separability generalizes Dirac\u2019s theorem. Discrete Appl. Math. 84(1\u20133), 43\u201353 (1998). https:\/\/doi.org\/10.1016\/S0166-218X(98)00005-5","journal-title":"Discrete Appl. Math."},{"key":"981_CR5","first-page":"1","volume-title":"Graph Theory and Sparse Matrix Computation, Volume 56 of IMA","author":"JRS Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.W.: An introduction to chordal graphs and clique trees. In: George, J.A., Gilbert, J.R., Liu, J.W.-H. (eds.) Graph Theory and Sparse Matrix Computation, Volume 56 of IMA, pp. 1\u201329. Springer, Berlin (1993)"},{"key":"981_CR6","doi-asserted-by":"publisher","unstructured":"Cao, Y.: Recognizing (unit) interval graphs by zigzag graph searches. In: Le Viet, H., King, V. (eds) Proceedings of the 4th SIAM Symposium on Simplicity in Algorithms (SOSA), pp. 92\u2013106. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976496.11","DOI":"10.1137\/1.9781611976496.11"},{"issue":"2","key":"981_CR7","doi-asserted-by":"publisher","first-page":"57","DOI":"10.46298\/dmtcs.2081","volume":"16","author":"P Charbit","year":"2014","unstructured":"Charbit, P., Habib, M., Mamcarz, A.: Influence of the tie-break rule on the end-vertex problem. Discrete Math. Theor. Comput. Sci. 16(2), 57\u201372 (2014). https:\/\/doi.org\/10.46298\/dmtcs.2081","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"981_CR8","doi-asserted-by":"publisher","unstructured":"Corneil, D.G.: Lexicographic breadth first search: a survey. In: Volume 3353 of LNCS, pp. 1\u201319. Springer (2004). https:\/\/doi.org\/10.1007\/978-3-540-30559-0_1","DOI":"10.1007\/978-3-540-30559-0_1"},{"issue":"3","key":"981_CR9","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/j.dam.2003.07.001","volume":"138","author":"DG Corneil","year":"2004","unstructured":"Corneil, D.G.: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discrete Appl. Math. 138(3), 371\u2013379 (2004). https:\/\/doi.org\/10.1016\/j.dam.2003.07.001","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"981_CR10","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1137\/11083856X","volume":"42","author":"DG Corneil","year":"2013","unstructured":"Corneil, D.G., Dalton, B., Habib, M.: LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs. SIAM J. Comput. 42(3), 792\u2013807 (2013). https:\/\/doi.org\/10.1137\/11083856X","journal-title":"SIAM J. Comput."},{"issue":"5","key":"981_CR11","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1016\/j.dam.2009.10.001","volume":"158","author":"DG Corneil","year":"2010","unstructured":"Corneil, D.G., K\u00f6hler, E., Lanlignel, J.-M.: On end-vertices of lexicographic breadth first searches. Discrete Appl. Math. 158(5), 434\u2013443 (2010). https:\/\/doi.org\/10.1016\/j.dam.2009.10.001","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"981_CR12","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/050623498","volume":"22","author":"DG Corneil","year":"2008","unstructured":"Corneil, D.G.: A unified view of graph searching. SIAM J. Discrete Math. 22(4), 1259\u20131276 (2008). https:\/\/doi.org\/10.1137\/050623498","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"981_CR13","doi-asserted-by":"publisher","first-page":"1284","DOI":"10.1137\/S0097539795282377","volume":"28","author":"DG Corneil","year":"1999","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: Linear time algorithms for dominating pairs in asteroidal triple-free graphs. SIAM J. Comput. 28(4), 1284\u20131297 (1999). https:\/\/doi.org\/10.1137\/S0097539795282377. (A preliminary version appeared in ICALP 1995)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"981_CR14","doi-asserted-by":"publisher","first-page":"1905","DOI":"10.1137\/S0895480100373455","volume":"23","author":"DG Corneil","year":"2009","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: The LBFS structure and recognition of interval graphs. SIAM J. Discrete Math. 23(4), 1905\u20131953 (2009). https:\/\/doi.org\/10.1137\/S0895480100373455. (A preliminary version appeared in SODA 1998)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"981_CR15","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"GA Dirac","year":"1961","unstructured":"Dirac, G.A.: On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg 25(1), 71\u201376 (1961). https:\/\/doi.org\/10.1007\/BF02992776","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg"},{"issue":"3","key":"981_CR16","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. Math. 15(3), 835\u2013855 (1965). https:\/\/doi.org\/10.2140\/pjm.1965.15.835","journal-title":"Pac. J. Math."},{"key":"981_CR17","doi-asserted-by":"publisher","unstructured":"Galinier, P., Habib, M., Paul, C.: Chordal graphs and their clique graphs. In: Nagl, M. (eds) Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 1017 of LNCS, pp. 358\u2013371. Springer (1995). https:\/\/doi.org\/10.1007\/3-540-60618-1_88","DOI":"10.1007\/3-540-60618-1_88"},{"issue":"1\u20132","key":"981_CR18","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M Habib","year":"2000","unstructured":"Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoret. Comput. Sci. 234(1\u20132), 59\u201384 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(97)00241-7","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"981_CR19","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"JE Hopcroft","year":"1974","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549\u2013568 (1974). https:\/\/doi.org\/10.1145\/321850.321852","journal-title":"J. ACM"},{"issue":"2","key":"981_CR20","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727. (A preliminary version appeared in CCC 1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"981_CR21","doi-asserted-by":"publisher","unstructured":"Kratsch, D., Liedloff, M., Meister, D.: End-vertices of graph search algorithms. In: Paschos, V.T., Widmayer, P. (eds) Proceedings of the 12th International Conference on Algorithms and Complexity (CIAC), volume 9079 of Lecture Notes in Computer Science, pp. 300\u2013312. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-319-18173-8_22","DOI":"10.1007\/978-3-319-18173-8_22"},{"issue":"3","key":"981_CR22","doi-asserted-by":"publisher","first-page":"23","DOI":"10.46298\/dmtcs.2094","volume":"16","author":"P Li","year":"2014","unstructured":"Li, P., Yaokun, W.: A four-sweep LBFS recognition algorithm for interval graphs. Discrete Math. Theor. Comput. Sci. 16(3), 23\u201350 (2014). https:\/\/doi.org\/10.46298\/dmtcs.2094","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"1","key":"981_CR23","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H Nagamochi","year":"1992","unstructured":"Nagamochi, H.: Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Discrete Math. 5(1), 54\u201366 (1992). https:\/\/doi.org\/10.1137\/0405004","journal-title":"SIAM J. Discrete Math."},{"key":"981_CR24","doi-asserted-by":"publisher","unstructured":"Nagamochi, H., Ibaraki, T.: Algorithmic aspects of graph connectivity. In: Encyclopedia of Mathematics and its Applications. Cambridge University Press (2008). https:\/\/doi.org\/10.1017\/CBO9780511721649","DOI":"10.1017\/CBO9780511721649"},{"issue":"2","key":"981_CR25","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266\u2013283 (1976). https:\/\/doi.org\/10.1137\/0205021. (A preliminary version appeared in STOC 1975)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"981_CR26","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1137\/0205005","volume":"5","author":"R Sethi","year":"1976","unstructured":"Sethi, R.: Scheduling graphs on two processors. SIAM J. Comput. 5(1), 73\u201382 (1976). https:\/\/doi.org\/10.1137\/0205005","journal-title":"SIAM J. Comput."},{"issue":"3","key":"981_CR27","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0166-218X(84)90008-8","volume":"7","author":"DR Shier","year":"1984","unstructured":"Shier, D.R.: Some aspects of perfect elimination orderings in chordal graphs. Discrete Appl. Math. 7(3), 325\u2013331 (1984). https:\/\/doi.org\/10.1016\/0166-218X(84)90008-8","journal-title":"Discrete Appl. Math."},{"key":"981_CR28","doi-asserted-by":"publisher","unstructured":"Simon, K.: A new simple linear algorithm to recognize interval graphs. In: Computational Geometry: Methods, Algorithms and Applications, International Workshop on Computational Geometry CG\u201991, Bern, Switzerland, March 21\u201322, pp. 289\u2013308 (1991). https:\/\/doi.org\/10.1007\/3-540-54891-2_22","DOI":"10.1007\/3-540-54891-2_22"},{"issue":"2","key":"981_CR29","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972). https:\/\/doi.org\/10.1137\/0201010. (A preliminary version appeared in SWAT (FOCS) 1971)","journal-title":"SIAM J. Comput."},{"key":"981_CR30","doi-asserted-by":"publisher","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3), 566\u2013579 (1984). With Addendum in the same Journal 14(1):254\u2013255 (1985.) https:\/\/doi.org\/10.1137\/0213035","DOI":"10.1137\/0213035"},{"key":"981_CR31","doi-asserted-by":"publisher","unstructured":"Tedder, M., Corneil, D.G., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Automata, Languages and Programming (ICALP), Volume 5125 of LNCS, pp. 634\u2013645. Berlin, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_52","DOI":"10.1007\/978-3-540-70575-8_52"},{"key":"981_CR32","doi-asserted-by":"publisher","first-page":"106176","DOI":"10.1016\/j.ipl.2021.106176","volume":"173","author":"M Zou","year":"2022","unstructured":"Zou, M., Wang, Z., Wang, J., Cao, Y.: End vertices of graph searches on bipartite graphs. Inf. Process. Lett. 173, 106176 (2022). https:\/\/doi.org\/10.1016\/j.ipl.2021.106176","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00981-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00981-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00981-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T14:16:26Z","timestamp":1660313786000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00981-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,21]]},"references-count":32,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["981"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00981-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,5,21]]},"assertion":[{"value":"28 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}