{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T14:55:56Z","timestamp":1743087356588,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031304477"},{"type":"electronic","value":"9783031304484"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-30448-4_10","type":"book-chapter","created":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T20:29:36Z","timestamp":1682368176000},"page":"127-141","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Enumeration of\u00a0Minimal Tropical Connected Sets"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2291-2556","authenticated-orcid":false,"given":"Ivan","family":"Bliznets","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3327-9768","authenticated-orcid":false,"given":"Danil","family":"Sagunov","sequence":"additional","affiliation":[]},{"given":"Eugene","family":"Tagin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,25]]},"reference":[{"issue":"2","key":"10_CR1","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1137\/19M1259638","volume":"34","author":"A Agrawal","year":"2020","unstructured":"Agrawal, A., Fomin, F.V., Lokshtanov, D., Saurabh, S., Tale, P.: Path contraction faster than $$2^n$$. SIAM J. Discret. Math. 34(2), 1302\u20131325 (2020)","journal-title":"SIAM J. Discret. Math."},{"issue":"5","key":"10_CR2","doi-asserted-by":"publisher","first-page":"1296","DOI":"10.1109\/TCBB.2011.19","volume":"8","author":"N Betzler","year":"2011","unstructured":"Betzler, N., Van Bevern, R., Fellows, M.R., Komusiewicz, C., Niedermeier, R.: Parameterized algorithmics for finding connected motifs in biological networks. IEEE\/ACM Trans. Comput. Biol. Bioinf. 8(5), 1296\u20131308 (2011)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"issue":"2","key":"10_CR3","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s00453-015-0054-2","volume":"76","author":"I Bliznets","year":"2016","unstructured":"Bliznets, I., Fomin, F.V., Pilipczuk, M., Villanger, Y.: Largest chordal and interval subgraphs faster than $$2^n$$. Algorithmica 76(2), 569\u2013594 (2016)","journal-title":"Algorithmica"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Bliznets, I., Sagunov, D.: Solving target set selection with bounded thresholds faster than $$2^n$$. Algorithmica, 1\u201322 (2022)","DOI":"10.1007\/s00453-022-01031-w"},{"key":"10_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-642-04241-6_2","volume-title":"Algorithms in Bioinformatics","author":"S B\u00f6cker","year":"2009","unstructured":"B\u00f6cker, S., Rasche, F., Steijger, T.: Annotating fragmentation patterns. In: Salzberg, S.L., Warnow, T. (eds.) WABI 2009. LNCS, vol. 5724, pp. 13\u201324. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04241-6_2"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. SIAM (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-319-13524-3_13","volume-title":"Parameterized and Exact Computation","author":"M Chapelle","year":"2014","unstructured":"Chapelle, M., Cochefert, M., Kratsch, D., Letourneur, R., Liedloff, M.: Exact exponential algorithms to find a tropical connected set of minimum size. In: Cygan, M., Heggernes, P. (eds.) IPEC 2014. LNCS, vol. 8894, pp. 147\u2013158. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-13524-3_13"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.tcs.2017.03.003","volume":"676","author":"M Chapelle","year":"2017","unstructured":"Chapelle, M., Cochefert, M., Kratsch, D., Letourneur, R., Liedloff, M.: Exact exponential algorithms to find tropical connected sets of minimum size. Theor. Comput. Sci. 676, 33\u201341 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10_CR9","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/s10878-019-00416-y","volume":"42","author":"J Cohen","year":"2021","unstructured":"Cohen, J., Italiano, G.F., Manoussakis, Y., Thang, N.K., Pham, H.P.: Tropical paths in vertex-colored graphs. J. Comb. Optim. 42(3), 476\u2013498 (2021)","journal-title":"J. Comb. Optim."},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.endm.2017.10.038","volume":"62","author":"J Cohen","year":"2017","unstructured":"Cohen, J., Manoussakis, Y., Phong, H., Tuza, Z.: Tropical matchings in vertex-colored graphs. Electron. Notes Discrete Math. 62, 219\u2013224 (2017)","journal-title":"Electron. Notes Discrete Math."},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1016\/j.tcs.2014.11.006","volume":"562","author":"JF Couturier","year":"2015","unstructured":"Couturier, J.F., Letourneur, R., Liedloff, M.: On the number of minimal dominating sets on some graph classes. Theoret. Comput. Sci. 562, 634\u2013642 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"10_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"2","key":"10_CR13","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s00453-013-9796-x","volume":"70","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Solving the 2-disjoint connected subgraphs problem faster than $$2^n$$. Algorithmica 70(2), 195\u2013207 (2014)","journal-title":"Algorithmica"},{"key":"10_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-642-13073-1_26","volume-title":"Algorithms and Complexity","author":"M Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M., Wojtaszczyk, J.O.: Irredundant set faster than O(2n). In: Calamoneri, T., Diaz, J. (eds.) CIAC 2010. LNCS, vol. 6078, pp. 288\u2013298. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13073-1_26"},{"issue":"23\u201324","key":"10_CR15","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1016\/j.ipl.2011.09.004","volume":"111","author":"M Cygan","year":"2011","unstructured":"Cygan, M., Pilipczuk, M., Wojtaszczyk, J.O.: Capacitated domination faster than $$o(2^n)$$. Inf. Process. Lett. 111(23\u201324), 1099\u20131103 (2011)","journal-title":"Inf. Process. Lett."},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.jda.2018.03.001","volume":"48","author":"JAA d\u2019Auriac","year":"2018","unstructured":"d\u2019Auriac, J.A.A., et al.: Tropical dominating sets in vertex-coloured graphs. J. Discrete Algorithms 48, 27\u201341 (2018)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"10_CR17","first-page":"327","volume":"17","author":"JAA d\u2019Auriac","year":"2016","unstructured":"d\u2019Auriac, J.A.A., Cohen, N., El Mafthoui, H., Harutyunyan, A., Legay, S., Manoussakis, Y.: Connected tropical subgraphs in vertex-colored graphs. Discrete Math. Theor. Comput. Sci. 17(3), 327\u2013348 (2016)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"10_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-540-73545-8_9","volume-title":"Computing and Combinatorics","author":"FV Fomin","year":"2007","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S.: Improved exact algorithms for counting 3- and 4-colorings. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 65\u201374. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73545-8_9"},{"issue":"1","key":"10_CR19","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/s00453-014-9914-4","volume":"73","author":"FV Fomin","year":"2015","unstructured":"Fomin, F.V., Giannopoulou, A.C., Pilipczuk, M.: Computing tree-depth faster than $$2^n$$. Algorithmica 73(1), 202\u2013216 (2015)","journal-title":"Algorithmica"},{"issue":"2","key":"10_CR20","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00453-007-9145-z","volume":"52","author":"FV Fomin","year":"2008","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Solving connected dominating set faster than $$2^n$$. Algorithmica 52(2), 153\u2013166 (2008)","journal-title":"Algorithmica"},{"issue":"1","key":"10_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1435375.1435384","volume":"5","author":"FV Fomin","year":"2008","unstructured":"Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.A.: Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Trans. Algorithms (TALG) 5(1), 1\u201317 (2008)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact exponential algorithms (2010)","DOI":"10.1007\/978-3-642-16533-7"},{"key":"10_CR23","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.dam.2019.07.015","volume":"278","author":"PA Golovach","year":"2020","unstructured":"Golovach, P.A., Heggernes, P., Kratsch, D., Saei, R.: Enumeration of minimal connected dominating sets for chordal graphs. Discrete Appl. Math. 278, 3\u201311 (2020). https:\/\/doi.org\/10.1016\/j.dam.2019.07.015","journal-title":"Discrete Appl. Math."},{"key":"10_CR24","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.tcs.2019.03.017","volume":"783","author":"PA Golovach","year":"2019","unstructured":"Golovach, P.A., Kratsch, D., Liedloff, M., Sayadi, M.Y.: Enumeration and maximum number of minimal dominating sets for chordal graphs. Theor. Comput. Sci. 783, 41\u201352 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2019.03.017","journal-title":"Theor. Comput. Sci."},{"key":"10_CR25","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Elsevier, Amsterdam (2004)"},{"issue":"3","key":"10_CR26","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","volume":"306","author":"P Heggernes","year":"2006","unstructured":"Heggernes, P.: Minimal triangulations of graphs: a survey. Discret. Math. 306(3), 297\u2013317 (2006)","journal-title":"Discret. Math."},{"key":"10_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-319-51963-0_17","volume-title":"SOFSEM 2017: Theory and Practice of Computer Science","author":"D Kratsch","year":"2017","unstructured":"Kratsch, D., Liedloff, M., Sayadi, M.Y.: Enumerating minimal tropical connected sets. In: Steffen, B., Baier, C., van den Brand, M., Eder, J., Hinchey, M., Margaria, T. (eds.) SOFSEM 2017. LNCS, vol. 10139, pp. 217\u2013228. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-51963-0_17"},{"issue":"8","key":"10_CR28","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1016\/j.ipl.2013.01.020","volume":"113","author":"M Krzywkowski","year":"2013","unstructured":"Krzywkowski, M.: Trees having many minimal dominating sets. Inf. Process. Lett. 113(8), 276\u2013279 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"10_CR29","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1109\/TCBB.2006.55","volume":"3","author":"V Lacroix","year":"2006","unstructured":"Lacroix, V., Fernandes, C.G., Sagot, M.F.: Motif search in graphs: application to metabolic networks. IEEE\/ACM Trans. Comput. Biol. Bioinf. 3(4), 360\u2013368 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"10_CR30","doi-asserted-by":"crossref","unstructured":"Lawer, E.L.: A note on the complexity of the chromatic number problem. Inf. Process. Lett. (1976)","DOI":"10.1016\/0020-0190(76)90065-X"},{"key":"10_CR31","unstructured":"Le, H., Highley, T.: Tropical vertex-disjoint cycles of a vertex-colored digraph: barter exchange with multiple items per agent. Discrete Math. Theor. Comput. Sci. 20 (2018)"},{"key":"10_CR32","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math. 3, 23\u201328 (1965)","journal-title":"Israel J. Math."},{"key":"10_CR33","doi-asserted-by":"crossref","unstructured":"Razgon, I.: Computing minimum directed feedback vertex set in $$o*(1.9977^n)$$. In: Theoretical Computer Science, pp. 70\u201381. World Scientific (2007)","DOI":"10.1142\/9789812770998_0010"},{"key":"10_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1007\/978-3-642-45043-3_36","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"JA Telle","year":"2013","unstructured":"Telle, J.A., Villanger, Y.: Connecting terminals and 2-disjoint connected subgraphs. In: Brandst\u00e4dt, A., Jansen, K., Reischuk, R. (eds.) WG 2013. LNCS, vol. 8165, pp. 418\u2013428. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-45043-3_36"},{"key":"10_CR35","unstructured":"Vassilevska Williams, V.: Hardness of easy problems: basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30448-4_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T23:03:49Z","timestamp":1684191829000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30448-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031304477","9783031304484"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30448-4_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"25 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Larnaca","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cyprus","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2023","order":10,"name":"conference_id","label":"Conference ID","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":"Easy Chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49","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":"25","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":"51% - 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","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":"6","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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3 invited papers","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}