{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T16:02:07Z","timestamp":1788883327113,"version":"build-2803163510"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2004,1]]},"abstract":"<jats:p>Recently, D. Corneil found a simple 3-sweep lexicographic breadth first search (LexBFS) algorithm for the recognition of proper interval graphs. We point out how to modify Corneil's algorithm to make it a certifying algorithm, and then describe a similar certifying 3-sweep LexBFS algorithm for the recognition of proper interval bigraphs. It follows from an earlier paper that the class of proper interval bigraphs is equal to the better known class of bipartite permutation graphs, and so we have a certifying algorithm for that class as well. All our algorithms run in time O(m+n), including the certification phase. The certificates of representability (the intervals) can be authenticated in time O(m+n). The certificates of nonrepresentability (the forbidden subgraphs) can be authenticated in time O(n).<\/jats:p>","DOI":"10.1137\/s0895480103430259","type":"journal-article","created":{"date-parts":[[2005,3,14]],"date-time":"2005-03-14T22:45:12Z","timestamp":1110840312000},"page":"554-570","source":"Crossref","is-referenced-by-count":43,"title":["Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs"],"prefix":"10.1137","volume":"18","author":[{"given":"Pavol","family":"Hell","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796"},{"key":"R2","unstructured":"A. Bretscher, D. G. Corneil, M. Habib, and C. Paul,\n                      A Simple LexBFS Based Cograph Recognition Algorithm\n                      , manuscript."},{"key":"R3","unstructured":"DavidBrown, StephenFlink, J.Lundgren, Characterizations of interval bigraphs and unit interval bigraphs, Proceedings of the Thirty\u2010third Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002), Vol. 157, 2002, 79\u2013932004e:05156"},{"key":"R4","unstructured":"D. E. Brown and J. R. Lundgren,\n                      Several Characterizations of Unit Interval Bigraphs\n                      , manuscript, 2003."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Jou\u2010MingChang, Chin\u2010WenHo, Ming\u2010TatKo, LexBFS\u2010ordering in asteroidal triple\u2010free graphs, Lecture Notes in Comput. Sci., Vol. 1741, Springer, Berlin, 1999, 163\u20131721793527","DOI":"10.1007\/3-540-46632-0_17"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195291230"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.07.001"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00046-F"},{"key":"R9","unstructured":"D. G. Corneil, S. Olariu, and L. Stewart,\n                      A Multisweep LBFS Algorithm for the Recognition of Interval Graphs\n                      , manuscript."},{"key":"R10","unstructured":"D. G. Corneil,\n                      private communication\n                      , 2003."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus, P. L. Hammer, F. Maffray, and S. Olariu,\n                      On domination elimination orderings and domination graphs\n                      , in Proceedings of the 20th International Workshop in Graph\u2010Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 903, Springer\u2010Verlag, Berlin, 1994, pp. 81\u201392.","DOI":"10.1007\/3-540-59071-4_39"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792269095"},{"key":"R13","unstructured":"F. F. Dragan and F. Nicolai,\n                      LexBFS\u2010Orderings of Distance\u2010Hereditary Graphs\n                      , Math. Tech. Report, SM\u2010DU\u2010322, University of Duisburg, Germany, 1996."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00133-W"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00241-7"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190200312"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20006"},{"key":"R18","unstructured":"DieterKratsch, RossMcConnell, KurtMehlhorn, JeremySpinrad, Certifying algorithms for recognizing interval graphs and permutation graphs, ACM, New York, 2003, 158\u20131671974915"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00014-5"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(93)90308-I"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0216057"},{"key":"R22","unstructured":"T. Ma, unpublished manuscript related to problems withi\u00b8tesimon."},{"key":"R23","unstructured":"R. M. McConnell,\n                      A certifying algorithm for the consecutive\u2010ones property\n                      , in Proceedings of the Fifteenth Annual ACM\u2010SIAM Symposium on Discrete Algorithms, New Orleans, LA, 2004, pp. 761\u2013770."},{"key":"R24","unstructured":"D. Meister,\n                      Recognition and computation of minimal triangulations for AT\u2010free, claw\u2010free and co\u2010comparability graphs\n                      , Discrete Appl. Math., to appear."},{"key":"R25","unstructured":"FredRoberts, Indifference graphs, Academic Press, New York, 1969, 139\u201314640:5488"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480190177145"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"K. Simon,\n                      A new simple linear algorithm to recognize interval graphs\n                      , in International Workshop on Computational Geometry CG'91, Bern, Switzerland, 1991, H. Bieri and H. Noltemeyer, eds., Lecture Notes in Comput. Sci. 553, Springer\u2010Verlag, Berlin, 1992, pp. 289\u2013308.","DOI":"10.1007\/3-540-54891-2_22"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1090\/fim\/019"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(87)80003-3"},{"key":"R31","unstructured":"AlanSprague, Recognition of bipartite permutation graphs, Proceedings of the Twenty\u2010sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995), Vol. 112, 1995, 151\u201316196j:05102"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/0214020"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1145\/268999.269003"},{"key":"R35","unstructured":"G. Wegner,\n                      Eigenschaften der nerven homologische\u2010einfactor familien inRn\n                      , Ph.D. thesis, Universit\u00e4t Gottingen, Germany, 1967."},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)81840-7"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480103430259","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:01:10Z","timestamp":1787320870000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480103430259"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1137\/S0895480103430259"],"URL":"https:\/\/doi.org\/10.1137\/s0895480103430259","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}