{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T19:56:09Z","timestamp":1760385369763},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T00:00:00Z","timestamp":1404172800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,2]]},"DOI":"10.1007\/s00224-014-9558-4","type":"journal-article","created":{"date-parts":[[2014,6,30]],"date-time":"2014-06-30T07:42:55Z","timestamp":1404114175000},"page":"394-405","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Sitting Closer to Friends than Enemies, Revisited"],"prefix":"10.1007","volume":"56","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakub Onufry","family":"Wojtaszczyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,7,1]]},"reference":[{"issue":"3","key":"9558_CR1","doi-asserted-by":"crossref","first-page":"036121","DOI":"10.1103\/PhysRevE.72.036121","volume":"72","author":"T Antal","year":"2005","unstructured":"Antal, T., Krapivsky, P.L., Redner, S.: Dynamics of social balance on networks. Phys. Rev. E 72(3), 036121 (2005)","journal-title":"Phys. Rev. E"},{"key":"9558_CR2","doi-asserted-by":"crossref","unstructured":"Belmonte, R., Vatshelle, M.: Graph classes with structured neighborhoods and algorithmic applications. In: Kolman, P., Kratochv\u00edl, J. (eds.), WG, volume 6986 of Lecture Notes in Computer Science, pp. 47\u201358. Springer (2011)","DOI":"10.1007\/978-3-642-25870-1_6"},{"issue":"5","key":"9558_CR3","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1037\/h0046049","volume":"63","author":"D Cartwright","year":"1956","unstructured":"Cartwright, D., Harary, F.: Structural balance: a generalization of heider\u2019s theory. Psychol Rev 63(5), 277\u2013293 (1956)","journal-title":"Psychol Rev"},{"issue":"2","key":"9558_CR4","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0020-0190(95)00046-F","volume":"55","author":"DG Corneil","year":"1995","unstructured":"Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P.: Simple linear time recognition of unit interval graphs. Inf. Process. Lett. 55(2), 99\u2013104 (1995)","journal-title":"Inf. Process. Lett."},{"key":"9558_CR5","doi-asserted-by":"crossref","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Sitting closer to friends than enemies, revisited. In: Rovan, B., Sassone, V., Widmayer, P. (eds.), MFCS, volume 7464 of Lecture Notes in Computer Science, pp. 296\u2013307. Springer (2012)","DOI":"10.1007\/978-3-642-32589-2_28"},{"issue":"2","key":"9558_CR6","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1177\/001872676702000206","volume":"20","author":"JA Davis","year":"1967","unstructured":"Davis, J.A.: Clustering and structural balance in graphs. Hum. Relat. 20(2), 181 (1967)","journal-title":"Hum. Relat."},{"key":"9558_CR7","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Mumford, E.: Self-overlapping curves revisited. In: Mathieu, C. (ed.), SODA, pp. 160\u2013169. SIAM (2009)","DOI":"10.1137\/1.9781611973068.19"},{"key":"9558_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"issue":"4","key":"9558_CR9","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1109\/TCBB.2010.77","volume":"8","author":"S Guillemot","year":"2011","unstructured":"Guillemot, S., Jansson, J., Sung, W.-K.: Computing a smallest multilabeled phylogenetic tree from rooted triplets. IEEE\/ACM Trans. Comput. Biol. Bioinform. 8(4), 1141\u20131147 (2011)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"18","key":"9558_CR10","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1016\/j.ipl.2009.07.010","volume":"109","author":"L Ibarra","year":"2009","unstructured":"Ibarra, L.: A simple algorithm to find hamiltonian cycles in proper interval graphs. Inf. Process. Lett. 109(18), 1105\u20131108 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9558_CR11","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62 (2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9558_CR12","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9558_CR13","doi-asserted-by":"crossref","unstructured":"Ioannidou, K., Mertzios, G.B., Nikolopoulos, S.D.: The longest path problem is polynomial on interval graphs. In: Kr\u00e1lovic, R., Niwinski, D. (eds.), MFCS, volume 5734 of Lecture Notes in Computer Science, pp. 403\u2013414. Springer (2009)","DOI":"10.1007\/978-3-642-03816-7_35"},{"key":"9558_CR14","doi-asserted-by":"crossref","unstructured":"Kermarrec, A.-M., Thraves, C.: Can everybody sit closer to their friends than their enemies? In: Murlak, F., Sankowski, P. (eds.) MFCS, volume 6907 of Lecture Notes in Computer Science, pp. 388\u2013399. Springer (2011)","DOI":"10.1007\/978-3-642-22993-0_36"},{"key":"9558_CR15","doi-asserted-by":"crossref","unstructured":"Kunegis, J., Schmidt, S., Lommatzsch, A., Lerner, J., Luca, E.W. De, Albayrak, S.: Spectral analysis of signed graphs for clustering, prediction and visualization. In: SDM, p. 559. SIAM (2010)","DOI":"10.1137\/1.9781611972801.49"},{"key":"9558_CR16","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Huttenlocher, D.P., Kleinberg, J.M.: Governance in social media: A case study of the wikipedia promotion process. In: Cohen, W.W., Gosling, S. (eds.) ICWSM. The AAAI Press (2010)","DOI":"10.1609\/icwsm.v4i1.14013"},{"key":"9558_CR17","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Huttenlocher, D.P., Kleinberg, J.M.: Predicting positive and negative links in online social networks. In: Rappa, M., Jones, P., Freire, J., Chakrabarti, S. (eds.), WWW, pp. 641\u2013650. ACM (2010)","DOI":"10.1145\/1772690.1772756"},{"key":"9558_CR18","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Huttenlocher, D.P., Kleinberg, J.M.: Signed networks in social media. In: Mynatt, E.D., Schoner, D., Fitzpatrick, G., Hudson, S.E., Edwards, W.K., Rodden, T. (eds.), CHI, pp. 1361\u20131370. ACM (2010)","DOI":"10.1145\/1753326.1753532"},{"issue":"7","key":"9558_CR19","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0898-1221(93)90308-I","volume":"25","author":"PJ Looges","year":"1993","unstructured":"Looges, P.J., Olariu, S.: Optimal greedy algorithms for indifference graphs. Comput. Math. Appl. 25(7), 15\u201325 (1993)","journal-title":"Comput. Math. Appl."},{"key":"9558_CR20","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.endm.2006.08.020","volume":"26","author":"B George","year":"2006","unstructured":"George, B.: Mertzios. A polynomial algorithm for the k-cluster problem on the interval graphs. Electron. Notes Discret. Math. 26, 111\u2013118 (2006)","journal-title":"Electron. Notes Discret. Math."},{"issue":"31","key":"9558_CR21","doi-asserted-by":"crossref","first-page":"13636","DOI":"10.1073\/pnas.1004008107","volume":"107","author":"M Szell","year":"2010","unstructured":"Szell, M., Lambiotte, R., Thurner, S.: Multirelational organization of large-scale social networks in an online world. PNAS 107 (31), 13636\u201313641 (2010)","journal-title":"PNAS"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9558-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9558-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9558-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T18:52:51Z","timestamp":1689360771000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9558-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,1]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,2]]}},"alternative-id":["9558"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9558-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7,1]]}}}