{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:46:23Z","timestamp":1759063583685},"reference-count":39,"publisher":"Elsevier BV","issue":"2-3","license":[{"start":{"date-parts":[[2003,6,1]],"date-time":"2003-06-01T00:00:00Z","timestamp":1054425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3735,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2003,6]]},"DOI":"10.1016\/s0166-218x(02)00499-7","type":"journal-article","created":{"date-parts":[[2003,5,12]],"date-time":"2003-05-12T23:10:20Z","timestamp":1052781020000},"page":"355-373","source":"Crossref","is-referenced-by-count":7,"title":["Recognition of some perfectly orderable graph classes"],"prefix":"10.1016","volume":"128","author":[{"given":"Elaine","family":"M. Eschen","sequence":"first","affiliation":[]},{"given":"Julie","family":"L. Johnson","sequence":"additional","affiliation":[]},{"given":"Jeremy","family":"P. Spinrad","sequence":"additional","affiliation":[]},{"given":"R","family":"Sritharan","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(02)00499-7_BIB1","series-title":"Graph Classes: A Survey","author":"Brandst\u00e4dt","year":"1999"},{"key":"10.1016\/S0166-218X(02)00499-7_BIB2","series-title":"Topics on Perfect Graphs","first-page":"63","article-title":"Perfectly ordered graphs","author":"Chv\u00e1tal","year":"1984"},{"key":"10.1016\/S0166-218X(02)00499-7_BIB3","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/0095-8956(87)90010-4","article-title":"On the P4-structure of perfect graphs-III. Partner decompositions","volume":"43","author":"Chv\u00e1tal","year":"1987","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/S0166-218X(02)00499-7_BIB4","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1002\/jgt.3190110405","article-title":"Four classes of perfectly orderable graphs","volume":"11","author":"Chv\u00e1tal","year":"1987","journal-title":"J. Graph Theory"},{"key":"10.1016\/S0166-218X(02)00499-7_BIB5","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0166-218X(86)90043-0","article-title":"Generalized neighbourhoods and a class of perfectly orderable graphs","volume":"15","author":"Cochand","year":"1986","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB6","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","article-title":"Matrix multiplication via arithmetic progressions","volume":"9","author":"Coppersmith","year":"1990","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB7","series-title":"Proceedings of the CAAP \u201994","first-page":"68","article-title":"A new linear algorithm for modular decomposition","volume":"Vol. 787","author":"Cournier","year":"1994"},{"key":"10.1016\/S0166-218X(02)00499-7_BIB8","unstructured":"E. Dahlhaus, J. Gustedt, R.M. McConnell, Efficient and practical modular decomposition, Proceedings of the Eighth ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Lousiana USA, 1997, pp. 26\u201335."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB9","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus, P.L. Hammer, F. Maffray, S. Olariu, On domination elimination orderings and domination graphs, in: Proceedings of the WG \u201994, Lecture Notes in Computer Science, Vol. 903, Springer, Berlin, 1994, pp. 81\u201392.","DOI":"10.1007\/3-540-59071-4_39"},{"key":"10.1016\/S0166-218X(02)00499-7_BIB10","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","article-title":"On rigid circuit graphs","volume":"25","author":"Dirac","year":"1961","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"10.1016\/S0166-218X(02)00499-7_BIB11","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","article-title":"Incidence matrices and interval graphs","volume":"15","author":"Fulkerson","year":"1965","journal-title":"Pacific J. Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB12","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0020-0190(96)00134-2","article-title":"P4-laden graphs","volume":"60","author":"Giakoumakis","year":"1996","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB13","unstructured":"I.M. Gorgos, Characterization of quasitriangulated graphs, Technical Report, University of Kishinev, 1982."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB14","doi-asserted-by":"crossref","unstructured":"M.R. Henzinger, V. King, Randomized fully dynamic graph algorithms with polylogarithmic time per operation, Proceedings of the 27th ACM Symposium on the Theory of Computation, Las Vegas, Nevada, USA. 1995, pp. 519\u2013527.","DOI":"10.1145\/225058.225269"},{"key":"10.1016\/S0166-218X(02)00499-7_BIB15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0095-8956(88)90050-0","article-title":"Bipartable graphs","volume":"45","author":"Hertz","year":"1988","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/S0166-218X(02)00499-7_BIB16","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0012-365X(90)90176-I","article-title":"Bipolarizable graphs","volume":"81","author":"Hertz","year":"1990","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB17","unstructured":"C.T. Ho\u00e0ng, Personal correspondence."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB18","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/S0012-365X(99)00300-3","article-title":"On P4-transversals of perfect graphs","volume":"216","author":"Ho\u00e0ng","year":"1989","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB19","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1002\/jgt.3190120310","article-title":"On brittle graphs","volume":"12","author":"Ho\u00e0ng","year":"1988","journal-title":"J. Graph Theory"},{"key":"10.1016\/S0166-218X(02)00499-7_BIB20","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0012-365X(89)90200-8","article-title":"A note on perfect orders","volume":"74","author":"Ho\u00e0ng","year":"1989","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB21","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1002\/jgt.3190130407","article-title":"Some classes of perfectly orderable graphs","volume":"13","author":"Ho\u00e0ng","year":"1989","journal-title":"J. Graph Theory"},{"key":"10.1016\/S0166-218X(02)00499-7_BIB22","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0012-365X(89)90209-4","article-title":"P4-comparability graphs","volume":"74","author":"Ho\u00e0ng","year":"1989","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB23","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/S0304-3975(00)00005-0","article-title":"Finding houses and holes in graphs","volume":"259","author":"Ho\u00e0ng","year":"2001","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB24","doi-asserted-by":"crossref","unstructured":"J. Holm, K. de Lichtenberg, M. Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge and biconnectivity, Proceedings of the 30th ACM Symposium on the Theory of Computing, Dallas, Texas, USA, 1998, pp. 79\u201389.","DOI":"10.1145\/276698.276715"},{"key":"10.1016\/S0166-218X(02)00499-7_BIB25","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1016\/0196-8858(88)90019-X","article-title":"On the semi-perfect elimination","volume":"9","author":"Jamison","year":"1988","journal-title":"Adv. Appl. Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB26","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","article-title":"Modular decomposition and transitive orientation","volume":"201","author":"McConnell","year":"1999","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB27","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0012-365X(90)90251-C","article-title":"On the complexity of recognizing perfectly orderable graphs","volume":"80","author":"Middendorf","year":"1990","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB28","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02022041","article-title":"Algorithmic aspects of the substitution decomposition in optimization over relations, set systems, and Boolean functions","volume":"4","author":"M\u00f6hring","year":"1985","journal-title":"Ann. Oper. Res."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB29","first-page":"257","article-title":"Substitution decomposition for discrete structures and connections with combinatorial optimization","volume":"19","author":"M\u00f6hring","year":"1984","journal-title":"Ann. Discrete Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB30","unstructured":"S. Olariu, Results on perfect graphs, Ph.D. Thesis, School of Computer Science, McGill University, Montreal, 1986."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB31","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0012-365X(89)90208-2","article-title":"Weak bipolarizable graphs","volume":"74","author":"Olariu","year":"1989","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB32","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0012-365X(93)90513-S","article-title":"Quasi-brittle graphs, a new class of perfectly orderable graphs","volume":"113","author":"Olariu","year":"1992","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB33","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0020-0190(89)90107-5","article-title":"Welsh\u2013Powell opposition graphs","volume":"31","author":"Olariu","year":"1989","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB34","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0012-365X(86)90097-X","article-title":"A note on superbrittle graphs","volume":"61","author":"Preissmann","year":"1986","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB35","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1016\/0022-247X(70)90282-9","article-title":"Triangulated graphs and the elimination process","volume":"32","author":"Rose","year":"1970","journal-title":"J. Math. Anal. Appl."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB36","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","article-title":"Algorithmic aspects of vertex elimination on graphs","volume":"5","author":"Rose","year":"1976","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB37","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0166-218X(91)90030-Z","article-title":"Recognizing brittle graphs","volume":"31","author":"Sch\u00e4ffer","year":"1991","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB38","unstructured":"M. Thorup, Decremental dynamic connectivity, Proceedings of the Eighth ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Lousiana, USA, 1997, pp. 305\u2013313."},{"key":"10.1016\/S0166-218X(02)00499-7_BIB39","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1093\/comjnl\/10.1.85","article-title":"An upper bound on the chromatic number of a graph and its applications to timetabling problems","volume":"10","author":"Welsh","year":"1967","journal-title":"Comput. J."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02004997?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02004997?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,19]],"date-time":"2020-03-19T21:20:22Z","timestamp":1584652822000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X02004997"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,6]]},"references-count":39,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2003,6]]}},"alternative-id":["S0166218X02004997"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(02)00499-7","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2003,6]]}}}