{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T18:06:21Z","timestamp":1743098781585,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030868376"},{"type":"electronic","value":"9783030868383"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-86838-3_13","type":"book-chapter","created":{"date-parts":[[2021,9,19]],"date-time":"2021-09-19T22:05:30Z","timestamp":1632089130000},"page":"169-181","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Heuristic Approach to the Treedepth Decomposition Problem for Large Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8763-0045","authenticated-orcid":false,"given":"Sylwester","family":"Swat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9863-5412","authenticated-orcid":false,"given":"Marta","family":"Kasprzak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,9,20]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/BF01934264","volume":"34","author":"B Aspvall","year":"1994","unstructured":"Aspvall, B., Heggernes, P.: Finding minimum height elimination trees for interval graphs in polynomial time. BIT Numer. Math. 34, 484\u2013509 (1994)","journal-title":"BIT Numer. Math."},{"key":"13_CR2","doi-asserted-by":"publisher","unstructured":"Bannach, M., Berndt, S., Schuster, M., Wienobst, M.: Solver description of Fluid. In: 5th Parameterized Algorithms and Computational Experiments Challenge, PACE 2020 (2020). https:\/\/doi.org\/10.5281\/zenodo.3871709","DOI":"10.5281\/zenodo.3871709"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Castillo-Garcia, N., Fraire-Huacuja, H., Flores, J., Rangel, R., Gonzalez Barbosa, J., Carpio Valadez, J.: Comparative study on constructive heuristics for the vertex separation problem. Stud. Comput. Intell. 601, 465\u2013474 (2015)","DOI":"10.1007\/978-3-319-17747-2_35"},{"key":"13_CR4","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"13_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-319-07959-2_23","volume-title":"Experimental Algorithms","author":"J Dibbelt","year":"2014","unstructured":"Dibbelt, J., Strasser, B., Wagner, D.: Customizable contraction hierarchies. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 271\u2013282. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07959-2_23"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Galler, B.A., Fisher, M.J.: An improved equivalence algorithm. Commun. ACM 7, 301\u2013303 (1964). 364099.364331","DOI":"10.1145\/364099.364331"},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"1877","DOI":"10.1007\/978-0-387-09766-4_507","volume-title":"Encyclopedia of Parallel Computing","author":"A Gupta","year":"2011","unstructured":"Gupta, A.: Sparse direct methods. In: Padua, D. (ed.) Encyclopedia of Parallel Computing, pp. 1877\u20131886. Springer, Boston (2011). https:\/\/doi.org\/10.1007\/978-0-387-09766-4_507"},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"2177","DOI":"10.1137\/15M1034337","volume":"30","author":"G Gutin","year":"2016","unstructured":"Gutin, G., Jones, M., Wahlstrom, M.: The mixed Chinese postman problem parameterized by pathwidth and treedepth. SIAM J. Discret. Math. 30, 2177\u20132205 (2016)","journal-title":"SIAM J. Discret. Math."},{"key":"13_CR9","doi-asserted-by":"publisher","unstructured":"Hamann, M., Strasser, B.: Graph bisection with pareto-optimization. In: Proceedings of the Meeting on Algorithm Engineering and Experiments, ALENEX 2016, Arlington, USA, pp. 90\u2013102 (2016.) https:\/\/doi.org\/10.1137\/1.9781611974317.8","DOI":"10.1137\/1.9781611974317.8"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"1460","DOI":"10.1016\/j.disc.2015.03.008","volume":"338","author":"I Karpas","year":"2015","unstructured":"Karpas, I., Neiman, O., Smorodinsky, S.: On vertex rankings of graphs and its relatives. Discret. Math. 338, 1460\u20131467 (2015)","journal-title":"Discret. Math."},{"key":"13_CR11","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0167-8191(89)90064-1","volume":"11","author":"JW Liu","year":"1989","unstructured":"Liu, J.W.: Reordering sparse matrices for parallel elimination. Parallel Comput. 11, 73\u201391 (1989)","journal-title":"Parallel Comput."},{"key":"13_CR12","unstructured":"Manne, F.: An algorithm for computing an elimination tree of minimum height for a tree. Preprint at ResearchGate (1998)"},{"key":"13_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity: Graphs, Structures, and Algorithms","author":"J Nesetril","year":"2012","unstructured":"Nesetril, J., de Mendez, P.O.: Sparsity: Graphs, Structures, and Algorithms. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4"},{"key":"13_CR14","unstructured":"Pieck, J.: Formele definitie van een e-tree. Technische Hogeschool Eindhoven, memorandum 80\u201306 (1980)"},{"key":"13_CR15","unstructured":"Schrijver, A.: A course in combinatorial optimization. Preprint at ResearchGate (2003)"},{"key":"13_CR16","unstructured":"Strasser, B.: FlowCutter. In: 5th Parameterized Algorithms and Computational Experiments Challenge, PACE 2020 (2020). https:\/\/github.com\/ben-strasser\/flow-cutter-pace20"},{"key":"13_CR17","doi-asserted-by":"publisher","unstructured":"Trimble, J.: Tweed: a heuristic solver for treedepth. In: 5th Parameterized Algorithms and Computational Experiments Challenge, PACE 2020 (2020). https:\/\/doi.org\/10.5281\/zenodo.3881441","DOI":"10.5281\/zenodo.3881441"},{"key":"13_CR18","doi-asserted-by":"publisher","unstructured":"Wrochna, M.: Sallow - a heuristic algorithm for treedepth decompositions. In: 5th Parameterized Algorithms and Computational Experiments Challenge, PACE 2020, preprint arXiv:2006.07050 (2020). https:\/\/doi.org\/10.5281\/zenodo.3870565","DOI":"10.5281\/zenodo.3870565"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Yaveroglu, O., Fitzhugh, S., Kurant, M., Markopoulou, A., Butts, C., Przulj, N.: Ergm.graphlets: a package for ERG modeling based on graphlet statistics. J. Stat. Softw. 65 (2014)","DOI":"10.18637\/jss.v065.i12"},{"key":"13_CR20","unstructured":"Proceedings of the 15th International Symposium on Parameterized and Exact Computation, IPEC 2020, Leibniz International Proceedings in Informatics 180 (2020)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-86838-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T20:02:21Z","timestamp":1702065741000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-86838-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030868376","9783030868383"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-86838-3_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 September 2021","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":"Warsaw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 June 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"47","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair and OCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"73","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":"30","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":"41% - 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":"11","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":"The conference was held online due to the COVID-19 pandemic.","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)"}}]}}