{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:43:18Z","timestamp":1740123798643,"version":"3.37.3"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T00:00:00Z","timestamp":1691452800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T00:00:00Z","timestamp":1691452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Order"],"published-print":{"date-parts":[[2024,4]]},"DOI":"10.1007\/s11083-023-09641-x","type":"journal-article","created":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T09:02:13Z","timestamp":1691485333000},"page":"99-133","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications"],"prefix":"10.1007","volume":"41","author":[{"given":"J\u00e9r\u00e9mie","family":"Dusart","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8564-2314","authenticated-orcid":false,"given":"Michel","family":"Habib","sequence":"additional","affiliation":[]},{"given":"Derek G.","family":"Corneil","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,8]]},"reference":[{"key":"9641_CR1","first-page":"149","volume":"25C","author":"B Behrendt","year":"1988","unstructured":"Behrendt, B.: Maximal antichains in partially ordered sets. Ars Comb. 25C, 149\u2013157 (1988)","journal-title":"Ars Comb."},{"key":"9641_CR2","unstructured":"Birkhoff, G.: Lattice theory. Am. Math. Soc. 25(3), (1967)"},{"key":"9641_CR3","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes, a survey. SIAM Monogr. Discret. Math. Appl. (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"9641_CR4","doi-asserted-by":"crossref","unstructured":"Caspard, N., Leclerc, B., Monjardet, B.: Finite Ordered Sets Concepts, Results and Uses. Cambridge University Press (2012)","DOI":"10.1017\/CBO9781139005135"},{"issue":"3","key":"9641_CR5","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)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9641_CR6","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1137\/15M1012396","volume":"30","author":"DG Corneil","year":"2016","unstructured":"Corneil, D.G., Dusart, J., Habib, M., K\u00f6hler, E.: On the power of graph searching for cocomparability graphs. SIAM J. Discret. Math. 30(1), 569\u2013591 (2016)","journal-title":"SIAM J. Discret. Math."},{"key":"9641_CR7","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/050623498","volume":"22","author":"DG Corneil","year":"2008","unstructured":"Corneil, D.G., Krueger, R.: A unified view of graph searching. SIAM J. Disc. Math. 22, 1259\u20131276 (2008)","journal-title":"SIAM J. Disc. Math."},{"issue":"4","key":"9641_CR8","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)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9641_CR9","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. Discret. Math. 23(4), 1905\u20131953 (2009)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"9641_CR10","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1137\/16M1059837","volume":"32","author":"D Coudert","year":"2018","unstructured":"Coudert, D., Ducoffe, G.: Revisiting Decomposition by Clique Separators. SIAM J. Discret. Math. 32(1), 682\u2013694 (2018)","journal-title":"SIAM J. Discret. Math."},{"key":"9641_CR11","doi-asserted-by":"crossref","unstructured":"Crespelle, C., Todinca, I.: An $${O}(n^2)$$-time algorithm for the minimal interval completion problem. Theor. Comput. Sci. 494, 75\u201385 (2013)","DOI":"10.1016\/j.tcs.2012.12.031"},{"key":"9641_CR12","doi-asserted-by":"crossref","unstructured":"Davey, B.\u00a0A., Priestley, H.\u00a0A.: Introduction to Lattices and Order (2nd ed.). Cambridge University Press, (2002)","DOI":"10.1017\/CBO9780511809088"},{"issue":"3","key":"9641_CR13","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0166-218X(88)90075-3","volume":"20","author":"PM Dearing","year":"1988","unstructured":"Dearing, P.M., Shier, D.R., Warner, D.D.: Maximal chordal subgraphs. Discret. Appl. Math. 20(3), 181\u2013190 (1988)","journal-title":"Discret. Appl. Math."},{"key":"9641_CR14","doi-asserted-by":"crossref","unstructured":"Dilworth, R.P.: Some combinatorial problems on partially ordered sets. Proc. Symp. Appl. Math. (Ann. Math. Soc. Providence R.I.) 10, 85\u201390 (1960)","DOI":"10.1090\/psapm\/010\/0115940"},{"key":"9641_CR15","unstructured":"Dusart, J.: Graph Searches with Applications to Cocomparability Graphs. PhD thesis, Universit\u00e9 Paris Diderot, (2014)"},{"issue":"3","key":"9641_CR16","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/20M1327835","volume":"50","author":"J Dusart","year":"2021","unstructured":"Dusart, J., Corneil, D.G., Habib, M.: Corrigendum: LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs. SIAM J. Comput. 50(3), 1148\u20131153 (2021)","journal-title":"SIAM J. Comput."},{"key":"9641_CR17","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.dam.2015.07.016","volume":"216","author":"J Dusart","year":"2017","unstructured":"Dusart, J., Habib, M.: A new LBFS-based algorithm for cocomparability graph recognition. Discret. Appl. Math. 216, 149\u2013161 (2017)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"9641_CR18","doi-asserted-by":"publisher","first-page":"600","DOI":"10.2307\/2371374","volume":"63","author":"B Dushnik","year":"1941","unstructured":"Dushnik, B., Miller, E.W.: Partially ordered sets. Am. J. Math. 63(3), 600\u2013610 (1941)","journal-title":"Am. J. Math."},{"key":"9641_CR19","doi-asserted-by":"crossref","unstructured":"Fishburn, P.C.: Interval orders and interval graphs. Wiley, (1985)","DOI":"10.1016\/0012-365X(85)90042-1"},{"key":"9641_CR20","doi-asserted-by":"crossref","unstructured":"Galinier, P., Habib, M., Paul, C.: Chordal Graphs and Their Clique Graphs. WG95, Graph-Theoretic Concepts in Computer Science, 21st International Workshop, LNCS 1017. pp. 358\u2013371 (1995)","DOI":"10.1007\/3-540-60618-1_88"},{"key":"9641_CR21","unstructured":"Garbe, R.: Algorithmic aspects of interval orders. PhD Thesis, Univ. of Twente, Enschede, The Netherlands (1994)"},{"key":"9641_CR22","doi-asserted-by":"publisher","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"PC Gilmore","year":"1964","unstructured":"Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and of interval graphs. Canad. J. Math. 16, 539\u2013548 (1964)","journal-title":"Canad. J. Math."},{"key":"9641_CR23","volume-title":"Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. North-Holland Publishing Co., Amsterdam (2004)"},{"key":"9641_CR24","unstructured":"Gr\u00e4tzer, G.: General Lattice Theory. Birkh\u00e4user (1968)"},{"issue":"1\u20132","key":"9641_CR25","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. Theor. Comput. Sci. 234(1\u20132), 59\u201384 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9641_CR26","first-page":"47","volume":"11","author":"M Habib","year":"1991","unstructured":"Habib, M., M\u00f6hring, R.H.: Treewidth of cocomparability graphs and a new order-theoretic parameter. Order 11(3), 47\u201360 (1991)","journal-title":"Order"},{"key":"9641_CR27","unstructured":"Habib, M., Morvan, M., Pouzet, M., Rampon, J.-X.: Extensions intervallaires minimales. In: Compte Rendu \u00e0 l\u2019Acad\u00e9mie des Sciences Paris, pr\u00e9sent\u00e9 en septembre 91, par le Pr. G. Choquet, vol 313. pp. 893\u2013898 (1991)"},{"key":"9641_CR28","unstructured":"Habib, M., Morvan, M., Pouzet, M., Rampon, J.-X.: Incidence structures, coding and lattice of maximal antichains. Technical Report 92-079, LIRMM, (1992)"},{"key":"9641_CR29","doi-asserted-by":"crossref","unstructured":"Heggernes, P., Suchan, K., Todinca, I., Villanger, Y.: Minimal interval completions. In: Brodal, G.\u00a0S., Leonardi, S. (eds.) ESA. Lecture Notes in Computer Science, vol 3669. pp. 403\u2013414. Springer (2005)","DOI":"10.1007\/11561071_37"},{"issue":"1","key":"9641_CR30","doi-asserted-by":"publisher","first-page":"75","DOI":"10.21136\/CMJ.1991.102435","volume":"41","author":"J\u00e1n Jakub\u00edk","year":"1991","unstructured":"Jakub\u00edk, J\u00e1n.: Maximal antichains in a partially ordered set. Czechoslov. Math. J. 41(1), 75\u201384 (1991)","journal-title":"Czechoslov. Math. J."},{"key":"9641_CR31","doi-asserted-by":"crossref","unstructured":"K\u00f6hler, E., Mouatadid, L.: Linear time LexDFS on cocomparability graphs. In: Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings. pp. 319\u2013330 (2014)","DOI":"10.1007\/978-3-319-08404-6_28"},{"key":"9641_CR32","doi-asserted-by":"crossref","unstructured":"Krastch, D., Spinrad, J.: Between $$O(mn)$$ and $$0(n^{\\alpha })$$. SIAM J. Comput. 36(2), 310\u2013325 (2007)","DOI":"10.1137\/S0097539704441435"},{"issue":"3","key":"9641_CR33","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1137\/0406032","volume":"6","author":"D Kratsch","year":"1993","unstructured":"Kratsch, D., Stewart, L.: Domination on cocomparability graphs. SIAM J. Discret. Math. 6(3), 400\u2013417 (1993)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"9641_CR34","doi-asserted-by":"publisher","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C Lekkerkerker","year":"1962","unstructured":"Lekkerkerker, C., Boland, J.: Representation of a finite graph by a set of intervals on the real line. Fundam. Math. 51(1), 45\u201364 (1962)","journal-title":"Fundam. Math."},{"key":"9641_CR35","unstructured":"Ma, T.-H.: Unpublished manuscript. (1992)"},{"key":"9641_CR36","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1090\/S0002-9947-1975-0360386-3","volume":"203","author":"G Markowsky","year":"1975","unstructured":"Markowsky, G.: The factorization and representation of lattices. Trans. Am. Math. Soc. 203, 185\u2013200 (1975)","journal-title":"Trans. Am. Math. Soc."},{"key":"9641_CR37","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF00383950","volume":"9","author":"G Markowsky","year":"1992","unstructured":"Markowsky, G.: Primes, irreductibles and extremal lattices. Order 9, 265\u2013290 (1992)","journal-title":"Order"},{"issue":"1\u20133","key":"9641_CR38","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.: Modular decomposition and transitive orientation. Discret. Math. 201(1\u20133), 189\u2013241 (1999)","journal-title":"Discret. Math."},{"issue":"3","key":"9641_CR39","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/j.dam.2004.10.001","volume":"146","author":"D Meister","year":"2005","unstructured":"Meister, D.: Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs. Discret. Appl. Math. 146(3), 193\u2013218 (2005)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"9641_CR40","doi-asserted-by":"publisher","first-page":"940","DOI":"10.1137\/100793529","volume":"26","author":"GB Mertzios","year":"2012","unstructured":"Mertzios, G.B., Corneil, D.G.: A simple polynomial algorithm for the longest path problem on cocomparability graphs. SIAM J. Discret. Math. 26(3), 940\u2013963 (2012)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"9641_CR41","doi-asserted-by":"publisher","first-page":"2820","DOI":"10.1137\/17M1120920","volume":"32","author":"GB Mertzios","year":"2018","unstructured":"Mertzios, G.B., Nichterlein, A., Niedermeier, R.: A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs. SIAM J. Discret. Math. 32(4), 2820\u20132835 (2018)","journal-title":"SIAM J. Discret. Math."},{"key":"9641_CR42","doi-asserted-by":"crossref","unstructured":"M\u00f6hring, R.H.: Algorithmic aspects of comparability graphs and interval graphs. In: Rival, I. (ed.) Graphs and Order. NATO ASI Series, vol. 147, pp. 41\u2013101. Springer Netherlands (1985)","DOI":"10.1007\/978-94-009-5315-4_2"},{"issue":"3","key":"9641_CR43","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0166-218X(95)00095-9","volume":"64","author":"RH M\u00f6hring","year":"1996","unstructured":"M\u00f6hring, R.H.: Triangulating graphs without asteroidal triples. Discrete Appl. Math. 64(3), 281\u2013287 (1996)","journal-title":"Discrete Appl. Math."},{"key":"9641_CR44","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0208031","volume":"8","author":"CH Papadimitriou","year":"1979","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Scheduling interval ordered tasks. SIAM J. Comput. 8, 405\u2013409 (1979)","journal-title":"SIAM J. Comput."},{"key":"9641_CR45","unstructured":"Parra, A.: Structural and algorithmic aspects of chordal graph embeddings. PhD thesis, Technische Universit\u00e4t Berlin, 1996"},{"key":"9641_CR46","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0012-365X(91)90016-U","volume":"88","author":"K Reuter","year":"1991","unstructured":"Reuter, K.: The jump number and the lattice of maximal antichains. Discrete Mathematics 88, 289\u2013307 (1991)","journal-title":"Discrete Mathematics"},{"key":"9641_CR47","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, 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"key":"9641_CR48","doi-asserted-by":"crossref","unstructured":"Schr\u00f6der, B.\u00a0S.\u00a0W.: Ordered sets, an introduction. Birkh\u00e4user (2002)","DOI":"10.1007\/978-1-4612-0053-6"},{"key":"9641_CR49","doi-asserted-by":"crossref","unstructured":"Simon, K.: A New Simple Linear Algorithm to Recognize Interval Graphs. Work. Comput. Geom. 289\u2013308 (1991)","DOI":"10.1007\/3-540-54891-2_22"},{"key":"9641_CR50","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S1571-0653(04)00026-5","volume":"2","author":"WT Trotter","year":"1999","unstructured":"Trotter, W.T.: Combinatorial aspects of interval orders and interval graphs. Electron. Notes Discret. Math. 2, 153 (1999)","journal-title":"Electron. Notes Discret. Math."}],"container-title":["Order"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-023-09641-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11083-023-09641-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-023-09641-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,26]],"date-time":"2024-04-26T02:43:37Z","timestamp":1714099417000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11083-023-09641-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,8]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["9641"],"URL":"https:\/\/doi.org\/10.1007\/s11083-023-09641-x","relation":{},"ISSN":["0167-8094","1572-9273"],"issn-type":[{"type":"print","value":"0167-8094"},{"type":"electronic","value":"1572-9273"}],"subject":[],"published":{"date-parts":[[2023,8,8]]},"assertion":[{"value":"1 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}