{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T08:42:41Z","timestamp":1726044161784},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030307851"},{"type":"electronic","value":"9783030307868"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-30786-8_21","type":"book-chapter","created":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T17:22:57Z","timestamp":1568222577000},"page":"271-284","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Polynomial-Time Algorithm for the Independent Set Problem in $$\\{{P_{10}},C_4,C_6\\}$$ -Free Graphs"],"prefix":"10.1007","author":[{"given":"Edin","family":"Husi\u0107","sequence":"first","affiliation":[]},{"given":"Martin","family":"Milani\u010d","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,9,12]]},"reference":[{"issue":"1","key":"21_CR1","first-page":"12","volume":"19","author":"I Adler","year":"2017","unstructured":"Adler, I., Le, N.K., M\u00fcller, H., Radovanovi\u0107, M., Trotignon, N., Vu\u0161kovi\u0107, K.: On rank-width of (diamond, even hole)-free graphs. Discrete Math. Theor. Comput. Sci. 19(1), 12 (2017). Paper No. 24","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"21_CR2","unstructured":"Alekseev, V.E.: The effect of local constraints on the complexity of determination of the graph independence number. In: Combinatorial-Algebraic Methods in Applied Mathematics, pp. 3\u201313 (1982)"},{"issue":"1\u20133","key":"21_CR3","first-page":"3","volume":"135","author":"VE Alekseev","year":"2004","unstructured":"Alekseev, V.E.: Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Appl. Math. 135(1\u20133), 3\u201316 (2004). [mr1760726], Russian translations. II","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"21_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.dam.2003.09.003","volume":"145","author":"VE Alekseev","year":"2004","unstructured":"Alekseev, V.E., Lozin, V.V.: Augmenting graphs for independent sets. Discrete Appl. Math. 145(1), 3\u201310 (2004)","journal-title":"Discrete Appl. Math."},{"key":"21_CR5","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.dam.2017.11.029","volume":"237","author":"A Brandst\u00e4dt","year":"2018","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Maximum weight independent set for \n \n \n \n $$\\ell $$\n claw-free graphs in polynomial time. Discrete Appl. Math. 237, 57\u201364 (2018)","journal-title":"Discrete Appl. Math."},{"key":"21_CR6","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.dam.2016.06.016","volume":"231","author":"C Brause","year":"2017","unstructured":"Brause, C.: A subexponential-time algorithm for the maximum independent set problem in \n \n \n \n $$P_t$$\n -free graphs. Discrete Appl. Math. 231, 113\u2013118 (2017)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"21_CR7","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"21_CR8","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"issue":"4","key":"21_CR9","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"issue":"1\u20133","key":"21_CR10","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0166-218X(03)00395-0","volume":"132","author":"MU Gerber","year":"2003","unstructured":"Gerber, M.U., Hertz, A., Lozin, V.V.: Stable sets in two subclasses of banner-free graphs. Discrete Appl. Math. 132(1\u20133), 121\u2013136 (2003)","journal-title":"Discrete Appl. Math."},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0304-0208(08)72943-8","volume":"88","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Polynomial algorithms for perfect graphs. North-Holland Math. Stud. 88, 325\u2013356 (1984)","journal-title":"North-Holland Math. Stud."},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.1137\/1.9781611975482.77","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Andrzej Grzesik","year":"2019","unstructured":"Grzesik, A., Klimo\u0161ov\u00e1, T., Pilipczuk, M., Pilipczuk, M.: Polynomial-time algorithm for maximum weight independent set on \n \n \n \n $$P_6$$\n -free graphs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1257\u20131271. SIAM (2019)"},{"key":"21_CR13","series-title":"GERAD 25th Anniversary Series","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/0-387-25592-3_4","volume-title":"Graph Theory and Combinatorial Optimization","author":"A Hertz","year":"2005","unstructured":"Hertz, A., Lozin, V.V.: The maximum independent set problem and augmenting graphs. In: Avis, D., Hertz, A., Marcotte, O. (eds.) Graph Theory and Combinatorial Optimization. GERAD 25th Anniversary Series, vol. 8, pp. 69\u201399. Springer, New York (2005). \n https:\/\/doi.org\/10.1007\/0-387-25592-3_4"},{"key":"21_CR14","unstructured":"Husi\u0107, E.: The maximum independent set problem and equistable graphs. Master\u2019s thesis, University of Primorska (2017)"},{"issue":"4","key":"21_CR15","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1145\/321850.321853","volume":"21","author":"PGH Lehot","year":"1974","unstructured":"Lehot, P.G.H.: An optimal algorithm to detect a line graph and output its root graph. J. ACM 21(4), 569\u2013575 (1974)","journal-title":"J. ACM"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent set in \n \n \n \n $$P_5$$\n -free graphs in polynomial time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 570\u2013581. ACM, New York (2014)","DOI":"10.1137\/1.9781611973402.43"},{"issue":"13","key":"21_CR17","doi-asserted-by":"publisher","first-page":"2517","DOI":"10.1016\/j.dam.2008.03.008","volume":"156","author":"VV Lozin","year":"2008","unstructured":"Lozin, V.V., Milani\u010d, M.: On finding augmenting graphs. Discrete Appl. Math. 156(13), 2517\u20132529 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"21_CR18","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Ser. B 28(3), 284\u2013304 (1980)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"21_CR19","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0020-0190(96)00197-4","volume":"61","author":"R Mosca","year":"1997","unstructured":"Mosca, R.: Polynomial algorithms for the maximum stable set problem on particular classes of \n \n \n \n $$P_5$$\n -free graphs. Inf. Process. Lett. 61(3), 137\u2013143 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"21_CR20","first-page":"307","volume":"15","author":"S Poljak","year":"1974","unstructured":"Poljak, S.: A note on stable sets and colorings of graphs. Comment. Math. Univ. Carol. 15(2), 307\u2013309 (1974)","journal-title":"Comment. Math. Univ. Carol."},{"key":"21_CR21","unstructured":"Roussopoulos, N.: A max \n \n \n \n $$\\{{\\rm m, n}\\}$$\n algorithm for determining the graph H from its line graph C. Inf. Process. Lett. 2(4), 108\u2013112 (1973)"},{"issue":"1","key":"21_CR22","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90287-R","volume":"29","author":"N Sbihi","year":"1980","unstructured":"Sbihi, N.: Algorithme de recherche d\u2019un stable de cardinalit\u00e9 maximum dans un graphe sans \u00e9toile. Discrete Math. 29(1), 53\u201376 (1980)","journal-title":"Discrete Math."},{"issue":"2","key":"21_CR23","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55(2), 221\u2013232 (1985)","journal-title":"Discrete Math."},{"issue":"2","key":"21_CR24","doi-asserted-by":"publisher","first-page":"219","DOI":"10.2298\/AADM100812027V","volume":"4","author":"K Vu\u0161kovi\u0107","year":"2010","unstructured":"Vu\u0161kovi\u0107, K.: Even-hole-free graphs: a survey. Appl. Anal. Discrete Math. 4(2), 219\u2013240 (2010)","journal-title":"Appl. Anal. Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-30786-8_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T17:25:18Z","timestamp":1568222718000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-30786-8_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030307851","9783030307868"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-30786-8_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 September 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vall de N\u00faria","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"45","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2019a","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/wg2019.sau.thilikos.info\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","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":"87","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":"29","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":"33% - 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.4","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":"1-2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}