{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:47:48Z","timestamp":1770994068300,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540642305","type":"print"},{"value":"9783540697053","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0028546","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T02:33:39Z","timestamp":1132626819000},"page":"25-38","source":"Crossref","is-referenced-by-count":15,"title":["A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata"],"prefix":"10.1007","author":[{"given":"Michel","family":"Habib","sequence":"first","affiliation":[]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[]},{"given":"Laurent","family":"Viennoti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"key":"4_CR1","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman. Design and analysis of computer algorithms. Addison-Wesley, 1974."},{"key":"4_CR2","unstructured":"J. Amilhastre. Repr\u00e9sentation par automates de l'ensemble des solutions d'un probl\u00e8me de satisfaction de contraintes. Technical Report 94056, LIRMM, 1994."},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"K.S. Booth and G.S. Lueker. Testing for the consecutive ones property, interval graphs and graph planarity using pq-tree algorithms. J. Comput. and Syst. Sciences, 13:335\u2013379, 1976.","journal-title":"J. Comput. and Syst. Sciences"},{"key":"4_CR4","unstructured":"D.G Corneil, S. Olariu, and L. Stewart. The ultimate interval graph recognition algorithm. Extended abstract, 1997."},{"key":"4_CR5","unstructured":"E. Dahlhaus, J. Gustedt, and R.M. McConnell. Efficient and practical modular decomposition. In Proc. of SODA, 1997."},{"key":"4_CR6","unstructured":"M. Habib, R. McConnell, C. Paul, and L. Viennot. Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoritical Computer Science, 1997. to appear."},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"J.E. Hopcropft. A nlogn algorithm for minizing states in a finite automaton. Theory of Machine and Computations, pages 189\u2013196, 1971.","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"W.L. Hsu. A simple test for the consecutive ones property. In LNCS 650, pages 459\u2013468, 1992.","DOI":"10.1007\/3-540-56279-6_98"},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0218005","volume":"18","author":"N. Korte","year":"1989","unstructured":"N. Korte and R. M\u00f6hring. An incremental linear-time algorithm for recognizing interval graphs. SIAM J. of Comp., 18:68\u201381, 1989.","journal-title":"SIAM J. of Comp."},{"key":"4_CR10","first-page":"854","volume":"17","author":"A. Lubiw","year":"1987","unstructured":"A. Lubiw. Doubly lexical orderings of matrices. SIAM Journ. of Algebraic Disc.Meth., 17:854\u2013879, 1987.","journal-title":"SIAM Journ. of Algebraic Disc.Meth."},{"key":"4_CR11","unstructured":"R.M. McConnell and J.P. Spinrad. Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In Proc. of SODA, pages 536\u2013545, 1994."},{"key":"4_CR12","unstructured":"R.M. McConnell and J.P. Spinrad. Linear-time modular decomposition and efficient transitive orientation of undirected graphs. In Proc. of SODA, 1997."},{"issue":"6","key":"4_CR13","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"R. Paige and R.E. Tarjan. Three partition refinement algorithms. SIAM Journ. of Comput., 16(6):973\u2013989, 1987.","journal-title":"SIAM Journ. of Comput."},{"issue":"2","key":"4_CR14","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D. J. Rose","year":"1976","unstructured":"Donald J. Rose, R. Endre Tarjan, and George S. Leuker. Algorithmic aspects of vertex elimination on graphs. SIAM J. of Comp., 5(2):266\u2013283, June 1976.","journal-title":"SIAM J. of Comp."},{"key":"4_CR15","unstructured":"J.P. Spinrad. Graph partitioning. preprint, 1986."},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R.E. Tarjan","year":"1975","unstructured":"R.E. Tarjan. Efficiency of a good but not linear set union algorithm. J. of ACM, 22:215\u2013225, 1975.","journal-title":"J. of ACM"}],"container-title":["Lecture Notes in Computer Science","STACS 98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028546","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,18]],"date-time":"2019-03-18T18:43:29Z","timestamp":1552934609000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028546"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540642305","9783540697053"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/bfb0028546","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]}}}