{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T18:47:52Z","timestamp":1710269272159},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T00:00:00Z","timestamp":1498262400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Classif"],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s00357-017-9230-1","type":"journal-article","created":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T03:58:09Z","timestamp":1498276689000},"page":"191-222","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Robinsonian Matrices: Recognition Challenges"],"prefix":"10.1007","volume":"34","author":[{"given":"D.","family":"Fortin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,6,24]]},"reference":[{"issue":"3","key":"9230_CR1","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF02293050","volume":"8","author":"D AVIS","year":"1992","unstructured":"AVIS, D., and FUKUDA, K. (1992), \u201cA Pivoting Algorithm for Convex Hulls and Vertex Enumeration of Arrangements and Polyhedra\u201d, Discrete and Computational Geometry, 8(3), 295\u2013313.","journal-title":"Discrete and Computational Geometry"},{"issue":"1-3","key":"9230_CR2","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0166-218X(98)00005-5","volume":"84","author":"A BERRY","year":"1998","unstructured":"BERRY, A., and BORDAT, J.-P. (1998), \u201cSeparability Generalizes Dirac\u2019s Theorem\u201d, Discrete and Applied Mathematics, 84(1-3), 43\u201353.","journal-title":"Discrete and Applied Mathematics"},{"issue":"3","key":"9230_CR3","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS BOOTH","year":"1976","unstructured":"BOOTH, K.S., and LUEKER, G.S. (1976), \u201cTesting for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms\u201d, Journal of Computer and System Sciences, 13(3), 335\u2013379.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1-2, Ser. B","key":"9230_CR4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF01585868","volume":"82","author":"RE BURKARD","year":"1998","unstructured":"BURKARD, R.E., \u00c7ELA, E., ROTE, G., and WOEGINGER, G.J. (1998), \u201cThe Quadratic Assignment Problem with a Monotone Anti-Monge and a Symmetric Toeplitz Matrix: Easy and Hard Cases\u201d, Mathematical Programming, 82(1-2, Ser. B), 125\u2013158.","journal-title":"Mathematical Programming"},{"issue":"5","key":"9230_CR5","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1016\/j.orl.2012.06.005","volume":"40","author":"E \u00c7ELA","year":"2012","unstructured":"\u00c7ELA, E., DEINEKO, V.G., and WOEGINGER, G.J. (2012), \u201cAnother Well-Solvable Case of the QAP: Maximizing the Job Completion Time Variance\u201d, Operations Research Letters, 40(5), 356\u2013359.","journal-title":"Operations Research Letters"},{"issue":"2","key":"9230_CR6","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/s003579900015","volume":"14","author":"V CHEPOI","year":"1997","unstructured":"CHEPOI, V., and FICHET, B. (1997), \u201cRecognition of Robinsonian Dissimilarities\u201d, Journal of Classification, 14(2), 311\u2013325.","journal-title":"Journal of Classification"},{"issue":"3","key":"9230_CR7","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s00357-009-9041-0","volume":"26","author":"V CHEPOI","year":"2009","unstructured":"CHEPOI, V., FICHET, B., and SESTON, M. (2009), \u201cSeriation in the Presence of Errors: NP-Hardness of l\u221e-Fitting Robinson Structures to Dissimilarity Matrices\u201d, Journal of Classification, 26(3), 279\u2013296.","journal-title":"Journal of Classification"},{"issue":"3","key":"9230_CR8","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/j.dam.2003.07.001","volume":"138","author":"DG CORNEIL","year":"2004","unstructured":"CORNEIL, D.G. (2004), \u201cA Simple 3-Sweep LBFS Algorithm for the Recognition of Unit Interval Graphs\u201d, Discrete Applied Mathematics, 138(3), 371\u2013379.","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"9230_CR9","doi-asserted-by":"crossref","first-page":"1284","DOI":"10.1137\/S0097539795282377","volume":"28","author":"DG CORNEIL","year":"1999","unstructured":"CORNEIL, D.G., OLARIU, S., and STEWART, L. (1999), \u201cLinear Time Algorithms for Dominating Pairs in Asteroidal Triple-Free Graphs\u201d, SIAM Journal on Computing, 28(4), 1284\u20131297.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"9230_CR10","doi-asserted-by":"crossref","first-page":"1905","DOI":"10.1137\/S0895480100373455","volume":"23","author":"DG CORNEIL","year":"2009","unstructured":"CORNEIL, D.G., OLARIU, S. and STEWART, L., (2009\/10) \u201cThe LBFS Structure and Recognition of Interval Graphs\u201d, SIAM Journal on Discrete Mathematics, 23(4), 1905\u20131953.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9230_CR11","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/j.dam.2015.06.011","volume":"199","author":"DG CORNEIL","year":"2016","unstructured":"CORNEIL, D.G., DUSART, J., HABIB, M., MAMCARZ, A., and DE MONTGOLFIER, F. (2016), \u201cA Tie-Break Model for Graph Search\u201d, Discrete Applied Mathematics, 199, 89\u2013100.","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"9230_CR12","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1137\/0406041","volume":"6","author":"E DAHLHAUS","year":"1993","unstructured":"DAHLHAUS, E. (1993), \u201cFast Parallel Recognition of Ultrametrics and TreeMetrics\u201d, SIAM Journal on Discrete Mathematics, 6(4), 523\u2013532.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9230_CR13","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0024-3795(90)90393-Q","volume":"139","author":"BL DIETRICH","year":"1990","unstructured":"DIETRICH, B.L. (1990), \u201cMonge Sequences, Antimatroids, and the Transportation Problem with Forbidden Arcs\u201d, Linear Algebra and Its Applications, 139, 133\u2013145.","journal-title":"Linear Algebra and Its Applications"},{"issue":"1-3","key":"9230_CR14","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0012-365X(98)00005-3","volume":"189","author":"D FORTIN","year":"1998","unstructured":"FORTIN, D., and RUDOLF, R. (1998), \u201cWeak Monge Arrays in Higher Dimensions\u201d, Discrete Mathematics, 189(1-3), 105\u2013115.","journal-title":"Discrete Mathematics"},{"issue":"1-2","key":"9230_CR15","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M HABIB","year":"2000","unstructured":"HABIB, M., MCCONNELL, R., PAUL, C., and VIENNOT, L. (2000), \u201cLex-BFS and Partition Refinement, with Applications to Transitive Orientation, Interval Graph Recognition and Consecutive Ones Testing\u201d, Theoretical Computer Science, 234(1-2), 59\u201384.","journal-title":"Theoretical Computer Science"},{"issue":"1-3","key":"9230_CR16","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0012-365X(98)00315-X","volume":"201","author":"S HO\u015eTEN","year":"1999","unstructured":"HO\u015eTEN, S., and MORRIS, W.D. Jr. (1999), \u201cThe Order Dimension of the Complete Graph\u201d, Discrete Mathematics, 201(1-3), 133\u2013139.","journal-title":"Discrete Mathematics"},{"key":"9230_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2044-8317.1994.tb01023.x","volume":"47","author":"L HUBERT","year":"1994","unstructured":"HUBERT, L., and ARABIE, P. (1994), \u201cThe Analysis of Proximity Matrices Through Sums of Matrices Having (Anti)-Robinson Forms\u201d, British Journal of Mathematical and Statistical Psychology, 47, 1\u201340.","journal-title":"British Journal of Mathematical and Statistical Psychology"},{"issue":"1","key":"9230_CR18","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0166-218X(94)00019-A","volume":"63","author":"B KLINZ","year":"1995","unstructured":"KLINZ, B., RUDOLF, R., and WOEGINGER, G.J. (1995), \u201cOn the Recognition of Permuted Bottleneck Monge Matrices\u201d, Discrete Applied Mathematics, 63(1), 43\u201374.","journal-title":"Discrete Applied Mathematics"},{"key":"9230_CR19","doi-asserted-by":"crossref","unstructured":"K\u00d6HLER, E., and MOUATADID, L. (2014), \u201cLinear Time LexDFS on Cocomparability Graphs\u201d, in Algorithm Theory\u2014SWAT 2014, Vol. 8503, Lecture Notes in Computer Science, Springer, pp. 319\u2013330.","DOI":"10.1007\/978-3-319-08404-6_28"},{"issue":"1-3","key":"9230_CR20","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0012-365X(94)00091-V","volume":"151","author":"M LAURENT","year":"1996","unstructured":"LAURENT, M. (1996), \u201cGraphic Vertices of the Metric Polytope\u201d, Discrete Mathematics, 151(1-3), 131\u2013153.","journal-title":"Discrete Mathematics"},{"key":"9230_CR21","doi-asserted-by":"crossref","unstructured":"LAURENT, M., and SEMINAROTI, M. (2015a), A Lex-BFS-Based Recognition Algorithm for Robinsonian Matrices, Springer International Publishing, pp. 325\u2013338.","DOI":"10.1007\/978-3-319-18173-8_24"},{"issue":"1","key":"9230_CR22","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.orl.2014.12.009","volume":"43","author":"M LAURENT","year":"2015","unstructured":"LAURENT, M., and SEMINAROTI, M. (2015b), \u201cThe Quadratic Assignment Problem is Easy for Robinsonian Matrices with Toeplitz Structure\u201d, Operations Research Letters, 43(1), 103\u2013109.","journal-title":"Operations Research Letters"},{"key":"9230_CR23","unstructured":"LAURENT, M., and SEMINAROTI, M. (2016), \u201cSimilarity-First Search: A New Algorithm with Application To RobinsonianMatrix Recognition\u201d, CoRR, abs\/1601.03521, http:\/\/arxiv.org\/abs\/1601.03521 ."},{"key":"9230_CR24","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"CG LEKKERKERKER","year":"1962","unstructured":"LEKKERKERKER, C.G., and BOLAND, J.C. (1962\/1963), \u201cRepresentation of a Finite Graph by a Set of Intervals on the Real Line\u201d, Fundamenta Mathematicae, 51, 45\u201364.","journal-title":"Fundamenta Mathematicae"},{"issue":"3","key":"9230_CR25","first-page":"23","volume":"16","author":"P LI","year":"2014","unstructured":"LI, P., and WU, Y. (2014), \u201cA Four-Sweep LBFS Recognition Algorithm for Interval Graphs\u201d, Discrete Mathematics and Theoretical Computer Science, 16(3), 23\u201350.","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"9230_CR26","unstructured":"MCCONNELL, R.M., and SPINRAD, J.P. (1994), \u201cLinear-Time Modular Decomposition and Efficient Transitive Orientation of Comparability Graphs\u201d, in Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA, 1994), New York: ACM, pp. 536\u2013545."},{"issue":"3","key":"9230_CR27","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/s00357-014-9150-2","volume":"31","author":"P PR\u00c9A","year":"2014","unstructured":"PR\u00c9A, P., and FORTIN, D. (2014), \u201cAn Optimal Algorithm to Recognize Robinsonian Dissimilarities\u201d, Journal of Classification, 31(3), 351\u2013385.","journal-title":"Journal of Classification"},{"issue":"4","key":"9230_CR28","doi-asserted-by":"crossref","first-page":"293","DOI":"10.2307\/276978","volume":"16","author":"W ROBINSON","year":"1951","unstructured":"ROBINSON, W. (1951), \u201cA Method for Chronologically Ordering Archaeological Deposits\u201d, American Antiquity, 16(4), 293\u2013301.","journal-title":"American Antiquity"},{"issue":"2","key":"9230_CR29","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF01415751","volume":"42","author":"R RUDOLF","year":"1995","unstructured":"RUDOLF, R., and WOEGINGER, G.J. (1995), \u201cThe Cone of Monge Matrices: Extremal Rays and Applications\u201d, ZOR\u2014Mathematical Methods of Operations Research, 42(2), 161\u2013168.","journal-title":"ZOR\u2014Mathematical Methods of Operations Research"},{"issue":"1","key":"9230_CR30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1023\/A:1017979506314","volume":"21","author":"I TSEVENDORJ","year":"2001","unstructured":"TSEVENDORJ, I. (2001), \u201cPiecewise-Convex Maximization Problems: Global Optimality Conditions\u201d, Journal of Global Optimization, 21(1), 1\u201314.","journal-title":"Journal of Global Optimization"},{"issue":"13-14","key":"9230_CR31","doi-asserted-by":"crossref","first-page":"2189","DOI":"10.1016\/j.dam.2013.02.028","volume":"161","author":"S-J XU","year":"2013","unstructured":"XU, S.-J., LI, X., and LIANG, R. (2013), \u201cMoplex Orderings Generated by the LexDFS Algorithm\u201d, Discrete Applied Mathematics, 161(13-14), 2189\u20132195.","journal-title":"Discrete Applied Mathematics"}],"container-title":["Journal of Classification"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00357-017-9230-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00357-017-9230-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00357-017-9230-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,26]],"date-time":"2019-09-26T20:04:20Z","timestamp":1569528260000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00357-017-9230-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,24]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["9230"],"URL":"https:\/\/doi.org\/10.1007\/s00357-017-9230-1","relation":{},"ISSN":["0176-4268","1432-1343"],"issn-type":[{"value":"0176-4268","type":"print"},{"value":"1432-1343","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,24]]}}}