{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:50:18Z","timestamp":1762300218526,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,19]],"date-time":"2022-11-19T00:00:00Z","timestamp":1668816000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,11,19]],"date-time":"2022-11-19T00:00:00Z","timestamp":1668816000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100020884","name":"ANID","doi-asserted-by":"crossref","award":["AFB170001","1151265"],"award-info":[{"award-number":["AFB170001","1151265"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2023,1]]},"DOI":"10.1007\/s10878-022-00953-z","type":"journal-article","created":{"date-parts":[[2022,11,19]],"date-time":"2022-11-19T10:07:02Z","timestamp":1668852422000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The weighted sitting closer to friends than enemies problem in the line"],"prefix":"10.1007","volume":"45","author":[{"given":"Julio","family":"Aracena","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9909-5315","authenticated-orcid":false,"given":"Christopher","family":"Thraves Caro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,11,19]]},"reference":[{"unstructured":"Becerra R,Thraves Caro C(2019) On the sitting closer to friends than enemies problem in trees and an intersection model for strongly chordal graphs. arXiv preprint arXiv:1911.11494","key":"953_CR1"},{"unstructured":"Ben\u00edtez F, Aracena J, Thraves Caro C (2018) The sitting closer to friends than enemies problem in the circumference. arXiv preprint arXiv:1811.02699","key":"953_CR2"},{"key":"953_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth KS, Lueker GS (1976) QTesting for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J Comput Syst Sci 13:335\u2013379","journal-title":"J Comput Syst Sci"},{"key":"953_CR4","volume-title":"Branch-and-Bound applications in combinatorial data analysis","author":"MJ Brusco","year":"2006","unstructured":"Brusco MJ, Stahl S (2006) Branch-and-Bound applications in combinatorial data analysis. Springer, Berlin"},{"key":"953_CR5","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s003579900015","volume":"14","author":"V Chepoi","year":"1997","unstructured":"Chepoi V, Fichet B (1997) Recognition of Robinsonian dissimilarities. J Classif 14:311\u2013325","journal-title":"J Classif"},{"key":"953_CR6","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00453-009-9319-y","volume":"59","author":"V Chepoi","year":"2011","unstructured":"Chepoi V, Seston M (2011) Seriation in the presence of errors: A factor 16 approximation algorithm for $$l_{\\infty }$$-fitting Robinson structures to distances. Algorithmica 59:521\u2013568","journal-title":"Algorithmica"},{"key":"953_CR7","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s00357-009-9041-0","volume":"26","author":"V Chepoi","year":"2009","unstructured":"Chepoi V, Fichet B, Seston M (2009) Seriation in the presence of errors: NP-hardness of $$l_{\\infty }$$-fitting Robinson structures to dissimilarity matrices. J Classif 26:279\u2013296","journal-title":"J Classif"},{"key":"953_CR8","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/s00224-014-9558-4","volume":"56","author":"M Cygan","year":"2015","unstructured":"Cygan M, Pilipczuk M, Pilipczuk M, Wojtaszczyk JO (2015) Sitting closer to friends than enemies, revisited. Theory of Comput Syst 56:394\u2013405","journal-title":"Theory of Comput Syst"},{"doi-asserted-by":"crossref","unstructured":"Ding C, He X (2004) Linearized cluster assignment via spectral ordering. In: Proceedings of the twenty-first international conference on Machine learning, ACM, p\u00a030","key":"953_CR9","DOI":"10.1145\/1015330.1015407"},{"key":"953_CR10","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s00357-017-9230-1","volume":"34","author":"D Fortin","year":"2017","unstructured":"Fortin D (2017) Robinsonian matrices: recognition challenges. J Classif 34:191\u2013222","journal-title":"J Classif"},{"doi-asserted-by":"crossref","unstructured":"Hubert L, Arabie P, Meulman J (2001) Combinatorial data analysis: Optimization by dynamic programming, vol.\u00a06. SIAM","key":"953_CR11","DOI":"10.1137\/1.9780898718553"},{"doi-asserted-by":"crossref","unstructured":"Kermarrec A-M, Thraves Caro C (2011) Can everybody sit closer to their friends than their enemies? In: Proceedings of the 36th international symposium on mathematical foundations of computer science. Springer, pp\u00a0388\u2013399","key":"953_CR12","DOI":"10.1007\/978-3-642-22993-0_36"},{"key":"953_CR13","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.dam.2017.01.027","volume":"222","author":"M Laurent","year":"2017","unstructured":"Laurent M, Seminaroti M (2017) A Lex-BFS-based recognition algorithm for Robinsonian matrices. Discrete Appl Math 222:151\u2013165","journal-title":"Discrete Appl Math"},{"key":"953_CR14","doi-asserted-by":"publisher","first-page":"1765","DOI":"10.1137\/16M1056791","volume":"31","author":"M Laurent","year":"2017","unstructured":"Laurent M, Seminaroti M (2017) Similarity-first search: a new algorithm with application to Robinsonian matrix recognition. SIAM J Discrete Math 31:1765\u20131800","journal-title":"SIAM J Discrete Math"},{"doi-asserted-by":"crossref","unstructured":"Laurent M, Seminaroti M, Tanigawa S-I (2017) A structural characterization for certifying Robinsonian matrices. Electron J Combin 24(2)","key":"953_CR15","DOI":"10.37236\/6701"},{"key":"953_CR16","first-page":"70","volume":"3","author":"I Liiv","year":"2010","unstructured":"Liiv I (2010) Seriation and matrix reordering methods: An historical overview, statistical analysis and data mining: the ASA. Data Sci J 3:70\u201391","journal-title":"Data Sci J"},{"key":"953_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69280-2","volume-title":"Graphs and genes","author":"BG Mirkin","year":"1984","unstructured":"Mirkin BG, Rodin SN (1984) Graphs and genes. Springer-Verlag, Berlin"},{"key":"953_CR18","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10878-013-9604-1","volume":"29","author":"EG Pardo","year":"2015","unstructured":"Pardo EG, Soto M, Caro C. Thraves (2015) Embedding signed graphs in the line. J Comb Optim 29:451\u2013471","journal-title":"J Comb Optim"},{"doi-asserted-by":"crossref","unstructured":"Petrie WMF (1899) Sequences in prehistoric remains. J Anthropol Inst Great Britain Ireland, pp\u00a0295\u2013301","key":"953_CR19","DOI":"10.2307\/2843012"},{"key":"953_CR20","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/s00357-014-9150-2","volume":"31","author":"P Pr\u00e9a","year":"2014","unstructured":"Pr\u00e9a P, Fortin D (2014) An optimal algorithm to recognize Robinsonian dissimilarities. J Classif 31:351\u2013385","journal-title":"J Classif"},{"key":"953_CR21","first-page":"139","volume-title":"Proof techniques in graph theory","author":"FS Roberts","year":"1969","unstructured":"Roberts FS (1969) Indifference graphs. In: Harary F (ed) Proof techniques in graph theory. Academic Press, New York, pp 139\u2013146"},{"key":"953_CR22","doi-asserted-by":"publisher","first-page":"293","DOI":"10.2307\/276978","volume":"16","author":"WS Robinson","year":"1951","unstructured":"Robinson WS (1951) A method for chronologically ordering archaeological deposits. Am Antiq 16:293\u2013301","journal-title":"Am Antiq"},{"doi-asserted-by":"crossref","unstructured":"Spaen Q, Thraves Caro C, Velednitsky M (2020) The dimension of valid distance drawings of signed graphs. Discrete Comput Geom 63:158\u2013168","key":"953_CR23","DOI":"10.1007\/s00454-019-00114-w"},{"key":"953_CR24","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1016\/j.jcss.2004.04.003","volume":"69","author":"M Thorup","year":"2004","unstructured":"Thorup M (2004) Integer priority queues with decrease key in constant time and the single source shortest paths problem. J Comput Syst Sci 69:330\u2013353","journal-title":"J Comput Syst Sci"},{"key":"953_CR25","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1186\/1471-2105-9-155","volume":"9","author":"Y-J Tien","year":"2008","unstructured":"Tien Y-J, Lee Y-S, Wu H-M, Chen C-H (2008) Methods for simultaneously identifying coherent local clusters with smooth global patterns in gene expression profiles. BMC Bioinf 9:155","journal-title":"BMC Bioinf"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00953-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00953-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00953-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,4]],"date-time":"2023-02-04T07:45:00Z","timestamp":1675496700000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00953-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,19]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["953"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00953-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,11,19]]},"assertion":[{"value":"20 October 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"9"}}