{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T23:57:02Z","timestamp":1762300622499,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031556005"},{"type":"electronic","value":"9783031556012"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-55601-2_13","type":"book-chapter","created":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T19:02:17Z","timestamp":1709665337000},"page":"193-207","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parameterized Algorithms for\u00a0Minimum Sum Vertex Cover"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-2964-0368","authenticated-orcid":false,"given":"Shubhada","family":"Aute","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6213-8687","authenticated-orcid":false,"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,6]]},"reference":[{"key":"13_CR1","unstructured":"Bakken, O.R.: Arrangement problems parameterized by neighbourhood diversity. Master\u2019s thesis, The University of Bergen (2018)"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Batra, J., Farhadi, M., Tetali, P.: Improved approximations for min sum vertex cover and generalized min sum set cover. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 998\u20131005 (2021)","DOI":"10.1137\/1.9781611976465.62"},{"issue":"2","key":"13_CR3","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1006\/inco.1997.2677","volume":"140","author":"A Bar-Noy","year":"1998","unstructured":"Bar-Noy, A., Bellare, M., Halld\u00f3rsson, M.M., Shachnai, H., Tamir, T.: On chromatic sums and distributed resource allocation. Inf. Comput. 140(2), 183\u2013202 (1998)","journal-title":"Inf. Comput."},{"key":"13_CR4","unstructured":"Barenholz, U., Feige, U., Peleg, D., et al.: Improved approximation for min-sum vertex cover. 81, 06\u201307 (2006). http:\/\/wisdomarchive.wisdom.weizmann.ac.il"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Basiak, M., Bienkowski, M., Tatarczuk, A.: An improved deterministic algorithm for the online min-sum set cover problem. arXiv preprint arXiv:2306.17755 (2023)","DOI":"10.1007\/978-3-031-49815-2_4"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Bienkowski, M., Mucha, M.: An improved algorithm for online min-sum set cover. In: AAAI, pp. 6815\u20136822 (2023)","DOI":"10.1609\/aaai.v37i6.25835"},{"issue":"3\u20134","key":"13_CR7","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1080\/10556780108805818","volume":"15","author":"S Burer","year":"2001","unstructured":"Burer, S., Monteiro, R.D.: A projected gradient algorithm for solving the maxcut sdp relaxation. Optim. Methods Softw. 15(3\u20134), 175\u2013200 (2001)","journal-title":"Optim. Methods Softw."},{"issue":"40\u201342","key":"13_CR8","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoret. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"13_CR9","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0898-1221(84)90085-3","volume":"10","author":"FR Chung","year":"1984","unstructured":"Chung, F.R.: On optimal linear arrangements of trees. Comput. Math. Appl. 10(1), 43\u201360 (1984)","journal-title":"Comput. Math. Appl."},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/978-3-662-43948-7_34","volume-title":"Automata, Languages, and Programming","author":"MS Dregi","year":"2014","unstructured":"Dregi, M.S., Lokshtanov, D.: Parameterized complexity of bandwidth on trees. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) Automata, Languages, and Programming, pp. 405\u2013416. Springer Berlin Heidelberg, Berlin, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_34"},{"issue":"1","key":"13_CR11","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.jcss.2010.06.006","volume":"77","author":"C Dubey","year":"2011","unstructured":"Dubey, C., Feige, U., Unger, W.: Hardness results for approximating the bandwidth. J. Comput. Syst. Sci. 77(1), 62\u201390 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s00453-004-1110-5","volume":"40","author":"U Feige","year":"2004","unstructured":"Feige, U., Lov\u00e1sz, L., Tetali, P.: Approximating min sum set cover. Algorithmica 40, 219\u2013234 (2004)","journal-title":"Algorithmica"},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-540-92182-0_28","volume-title":"Algorithms and Computation","author":"MR Fellows","year":"2008","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) Algorithms and Computation, pp. 294\u2013305. Springer Berlin Heidelberg, Berlin, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-92182-0_28"},{"issue":"17","key":"13_CR14","doi-asserted-by":"publisher","first-page":"3166","DOI":"10.1016\/j.dam.2008.05.008","volume":"156","author":"H Fernau","year":"2008","unstructured":"Fernau, H.: Parameterized algorithmics for linear arrangement problems. Discret. Appl. Math. 156(17), 3166\u20133177 (2008)","journal-title":"Discret. Appl. Math."},{"key":"13_CR15","unstructured":"Fotakis, D., Kavouras, L., Koumoutsos, G., Skoulakis, S., Vardas, M.: The online min-sum set cover problem. In: 47th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 51:1\u201351:16 (2020)"},{"issue":"3","key":"13_CR16","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"MR Garey","year":"1978","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S., Knuth, D.E.: Complexity results for bandwidth minimization. SIAM J. Appl. Math. 34(3), 477\u2013495 (1978)","journal-title":"SIAM J. Appl. Math."},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified np-complete problems. In: Symposium on the Theory of Computing (STOC), pp. 47\u201363 (1974)","DOI":"10.1145\/800119.803884"},{"key":"13_CR18","unstructured":"Gavril, F.: Some np-complete problems on graphs. In: Proceedings of the Conference on Information Science and Systems, 1977, pp. 91\u201395 (1977)"},{"key":"13_CR19","volume-title":"Results on the min-sum vertex cover problem","author":"R Gera","year":"2006","unstructured":"Gera, R., Rasmussen, C., Stanica, P., Horton, S.: Results on the min-sum vertex cover problem. Tech. rep, NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF APPLIED MATHEMATICS (2006)"},{"key":"13_CR20","unstructured":"Gima, T., Kim, E.J., K\u00f6hler, N., Melissinos, N., Vasilakis, M.: Bandwidth parameterized by cluster vertex deletion number. arXiv preprint arXiv:2309.17204 (2023)"},{"issue":"4","key":"13_CR21","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1016\/0196-6774(84)90006-3","volume":"5","author":"EM Gurari","year":"1984","unstructured":"Gurari, E.M., Sudborough, I.H.: Improved dynamic programming algorithms for bandwidth minimization and the mincut linear arrangement problem. J. Algorithms 5(4), 531\u2013546 (1984)","journal-title":"J. Algorithms"},{"key":"13_CR22","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00224-007-1330-6","volume":"41","author":"G Gutin","year":"2007","unstructured":"Gutin, G., Rafiey, A., Szeider, S., Yeo, A.: The linear arrangement problem parameterized above guaranteed value. Theor. Comput. Syst. 41, 521\u2013538 (2007)","journal-title":"Theor. Comput. Syst."},{"issue":"1","key":"13_CR23","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0112012","volume":"12","author":"LH Harper","year":"1964","unstructured":"Harper, L.H.: Optimal assignments of numbers to vertices. J. Soc. Ind. Appl. Math. 12(1), 131\u2013135 (1964)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of computer computations Proc. Sympos., pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"13_CR25","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2- $$\\varepsilon $$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR26","unstructured":"Lokshtanov, D.: Parameterized integer quadratic programming: Variables and coefficients. arXiv preprint arXiv:1511.00310 (2015)"},{"issue":"3","key":"13_CR27","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1137\/0606044","volume":"6","author":"FS Makedon","year":"1985","unstructured":"Makedon, F.S., Papadimitriou, C.H., Sudborough, I.H.: Topological bandwidth. SIAM J. Algebraic Discr. Methods 6(3), 418\u2013444 (1985)","journal-title":"SIAM J. Algebraic Discr. Methods"},{"key":"13_CR28","doi-asserted-by":"crossref","unstructured":"Mohan, S.R., Acharya, B., Acharya, M.: A sufficiency condition for graphs to admit greedy algorithm in solving the minimum sum vertex cover problem. In: International Conference on Process Automation, Control and Computing, pp. 1\u20135. IEEE (2011)","DOI":"10.1109\/PACC.2011.5979021"},{"issue":"4","key":"13_CR29","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0607057","volume":"7","author":"B Monien","year":"1986","unstructured":"Monien, B.: The bandwidth minimization problem for caterpillars with hair length 3 is np-complete. SIAM J. Algebraic Discr. Methods 7(4), 505\u2013512 (1986)","journal-title":"SIAM J. Algebraic Discr. Methods"},{"issue":"3","key":"13_CR30","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02280884","volume":"16","author":"CH Papadimitriou","year":"1976","unstructured":"Papadimitriou, C.H.: The np-completeness of the bandwidth minimization problem. Computing 16(3), 263\u2013270 (1976)","journal-title":"Computing"},{"key":"13_CR31","unstructured":"Rasmussen, C.W.: On efficient construction of minimum-sum vertex covers (2006)"},{"key":"13_CR32","unstructured":"Stankovi\u0107, A.: Some results on approximability of minimum sum vertex cover. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2022). vol. 245, pp. 50:1\u201350:16 (2022)"},{"issue":"1","key":"13_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2004.12.001","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M., Bodlaender, H.L.: Cutwidth i: a linear time fixed parameter algorithm. J. Algorithms 56(1), 1\u201324 (2005)","journal-title":"J. Algorithms"},{"issue":"4","key":"13_CR34","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1145\/4221.4228","volume":"32","author":"M Yannakakis","year":"1985","unstructured":"Yannakakis, M.: A polynomial algorithm for the min-cut linear arrangement of trees. J. ACM (JACM) 32(4), 950\u2013988 (1985)","journal-title":"J. ACM (JACM)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2024: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-55601-2_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,13]],"date-time":"2024-11-13T21:35:31Z","timestamp":1731533731000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-55601-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031556005","9783031556012"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-55601-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"6 March 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Puerto Varas","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chile","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 March 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 March 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/latin2024.cmm.uchile.cl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"92","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"44","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"48% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}