{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:39:25Z","timestamp":1740145165669,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,11,13]],"date-time":"2017-11-13T00:00:00Z","timestamp":1510531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"JSPS Postdoctoral Fellowships for Research Abroad"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2020,3]]},"DOI":"10.1007\/s11590-017-1213-y","type":"journal-article","created":{"date-parts":[[2017,11,13]],"date-time":"2017-11-13T11:56:14Z","timestamp":1510574174000},"page":"339-353","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Perfect elimination orderings for symmetric matrices"],"prefix":"10.1007","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8474-2121","authenticated-orcid":false,"given":"Monique","family":"Laurent","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shin-ichi","family":"Tanigawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,11,13]]},"reference":[{"key":"1213_CR1","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0012-365X(95)00081-7","volume":"158","author":"A Brandst\u00e4dt","year":"1996","unstructured":"Brandst\u00e4dt, A., Chepoi, V., Dragan, F.: Perfect elimination orderings of chordal powers of graphs. Discret. Math. 158, 273\u2013278 (1996)","journal-title":"Discret. Math."},{"key":"1213_CR2","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1137\/S0895480193253415","volume":"11","author":"A Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Dragan, F., Chepoi, V., Voloshin, V.: Dually chordal graphs. SIAM J. Discret. Math. 11, 437\u2013455 (1998)","journal-title":"SIAM J. Discret. Math."},{"key":"1213_CR3","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0012-365X(96)00070-2","volume":"171","author":"A Brandst\u00e4dt","year":"1997","unstructured":"Brandst\u00e4dt, A., Dragan, F., Nicolai, F.: LexBFS-orderings and powers of chordal graphs. Discret. Math. 171, 27\u201342 (1997)","journal-title":"Discret. Math."},{"key":"1213_CR4","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0304-3975(03)00221-4","volume":"307","author":"LS Chandran","year":"2003","unstructured":"Chandran, L.S., Ibarra, L., Ruskey, F., Sawada, J.: Generating and characterizing the perfect elimination orderings of a chordal graph. Theor. Comput. Sci. 307, 303\u2013317 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"1213_CR5","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1137\/S0895480195291230","volume":"11","author":"V Chepoi","year":"1998","unstructured":"Chepoi, V.: On distance-preserving and domination elimination orderings. SIAM J. Discret. Math. 11, 414\u2013436 (1998)","journal-title":"SIAM J. Discret. Math."},{"key":"1213_CR6","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. Discret. Appl. Math. 138, 371\u2013379 (2004)","journal-title":"Discret. Appl. Math."},{"key":"1213_CR7","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. Abh. Math. Semin. Univ. Hambg. 25, 71\u201376 (1961)","journal-title":"Abh. Math. Semin. Univ. Hambg."},{"key":"1213_CR8","first-page":"67","volume":"4","author":"FF Dragan","year":"1992","unstructured":"Dragan, F.F., Prisacaru, C.F., Chepoi, V.D.: Location problems in graphs and the Helly property. Discret. Math. Mosc. 4, 67\u201373 (1992). (in Russian)","journal-title":"Discret. Math. Mosc."},{"key":"1213_CR9","first-page":"67","volume":"21","author":"P Duchet","year":"1984","unstructured":"Duchet, P.: Classical perfect graphs: an introduction with emphasis on triangulated and interval graphs. Ann. Discret. Math. 21, 67\u201396 (1984)","journal-title":"Ann. Discret. Math."},{"issue":"1","key":"1213_CR10","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(1), 149\u2013161 (2017)","journal-title":"Discret. Appl. Math."},{"key":"1213_CR11","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1137\/0607049","volume":"7","author":"M Farber","year":"1986","unstructured":"Farber, M., Jamison, R.E.: Convexity in graphs and hypergraphs. SIAM J. Algebr. Discret. Methods 7, 433\u2013444 (1986)","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"1213_CR12","first-page":"1","volume":"17","author":"F Fogel","year":"2016","unstructured":"Fogel, F., d\u2019Aspremont, A., Vojnovic, M.: Serialrank: spectral ranking using seriation. J. Mach. Learn. Res. 17, 1\u201345 (2016)","journal-title":"J. Mach. Learn. Res."},{"key":"1213_CR13","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, 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"issue":"22","key":"1213_CR14","doi-asserted-by":"publisher","first-page":"2906","DOI":"10.1016\/j.disc.2006.04.043","volume":"307","author":"G Gardi","year":"2007","unstructured":"Gardi, G.: The Roberts characterization of proper and unit interval graphs. Discret. Math. 307(22), 2906\u20132908 (2007)","journal-title":"Discret. Math."},{"issue":"2","key":"1213_CR15","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1(2), 180\u2013187 (1972)","journal-title":"SIAM J. Comput."},{"key":"1213_CR16","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0024-3795(84)90207-6","volume":"58","author":"R Grone","year":"1984","unstructured":"Grone, R., Johnson, C.R., S\u00e0, E.M., Wolkowicz, H.: Positive definite completions of partial Hermitian matrices. Linear Algebra Appl. 58, 109\u2013124 (1984)","journal-title":"Linear Algebra Appl."},{"key":"1213_CR17","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, 400\u2013417 (1993)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"1213_CR18","doi-asserted-by":"publisher","first-page":"1765","DOI":"10.1137\/16M1056791","volume":"31","author":"M Laurent","year":"2017","unstructured":"Laurent, M., Seminaroti, M.: Similarity-first search: a new algorithm with application to Robinsonian matrix recognition. SIAM J. Discret. Math. 31(3), 1765\u20131800 (2017)","journal-title":"SIAM J. Discret. Math."},{"key":"1213_CR19","doi-asserted-by":"crossref","unstructured":"Laurent, M., Seminaroti, M., Tanigawa, S.: A structural characterization for certifying Robinsonian matrices. Electron. J. Comb. 24(2), Paper #P2.21 (2017)","DOI":"10.37236\/6701"},{"issue":"2","key":"1213_CR20","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1002\/sam.10071","volume":"3","author":"I Liiv","year":"2010","unstructured":"Liiv, I.: Seriation and matrix reordering methods: an historical overview. Stat. Anal. Data Min. 3(2), 70\u201391 (2010)","journal-title":"Stat. Anal. Data Min."},{"key":"1213_CR21","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0020-0190(91)90245-D","volume":"37","author":"S Olariu","year":"1991","unstructured":"Olariu, S.: An optimal greedy heuristic to color interval graphs. Inf. Process. Lett. 37, 65\u201380 (1991)","journal-title":"Inf. Process. Lett."},{"key":"1213_CR22","unstructured":"Roberts, F.S.: Indifference graphs. In: Proof Techniques in Graph Theory: Proceedings of the Second Ann Arbor Graph Theory Conference, pp. 139\u2013146. Academic (1969)"},{"key":"1213_CR23","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D Rose","year":"1976","unstructured":"Rose, D., Lueker, G., Tarjan, R.E.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5, 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1213_CR24","doi-asserted-by":"publisher","first-page":"293","DOI":"10.2307\/276978","volume":"16","author":"WS Robinson","year":"1951","unstructured":"Robinson, W.S.: A method for chronologically ordering archaeological deposits. Am. Antiq. 16(4), 293\u2013301 (1951)","journal-title":"Am. Antiq."},{"issue":"1\u20133","key":"1213_CR25","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.tcs.2005.03.051","volume":"341","author":"J Sawada","year":"2005","unstructured":"Sawada, J.: Oracles for vertex elimination orderings. Theor. Comput. Sci. 341(1\u20133), 73\u201390 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"1213_CR26","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"RE Tarjan","year":"1984","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, 566\u2013579 (1984)","journal-title":"SIAM J. Comput."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-017-1213-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-017-1213-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-017-1213-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,28]],"date-time":"2024-06-28T16:07:18Z","timestamp":1719590838000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-017-1213-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,13]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["1213"],"URL":"https:\/\/doi.org\/10.1007\/s11590-017-1213-y","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2017,11,13]]},"assertion":[{"value":"17 April 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 November 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}