{"id":29,"date":"2025-06-11T13:07:15","date_gmt":"2025-06-11T13:07:15","guid":{"rendered":"https:\/\/taaresearchlunch.univie.ac.at\/?p=29"},"modified":"2025-06-11T13:07:42","modified_gmt":"2025-06-11T13:07:42","slug":"24-april-2025-martin-schirneck","status":"publish","type":"post","link":"https:\/\/taaresearchlunch.univie.ac.at\/?p=29","title":{"rendered":"08 May 2025 &#8211; Martin Schirneck"},"content":{"rendered":"\n<p><strong>Date:<\/strong> 08 May 2025<br><strong>Time:<\/strong> 11:45 &#8211; 12:45<br><strong>Location: <\/strong>Forschungslabor 3 (sofa room)<\/p>\n\n\n\n<p><strong>Speaker:<\/strong> Martin Schirneck<br><strong>Title:<\/strong> Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks<\/p>\n\n\n\n<p><strong>Abstract:<\/strong><br>This talk is about the design of fault-tolerant data structures that can report graph parameters like distances or connectivity even after some edges of the underlying graph G have failed. An important tool in the area are (L,f)-replacement path coverings (RPCs). These are families of subgraphs of G that guarantee the following property for every set F of at most f edge failures and every pair of vertices s and t: If there is a shortest s-t-path in the graph G-F that has at most L edges, then at least one subgraph in  the RPC contains no edge of F but all edges of this replacement path. We present a new construction of (L,f)-replacement path coverings whose parameters improve over previous works by Weimann and Yuster  [FOCS 2010] as well as Karthik and Parter [SODA 2021]. We then briefly discuss how this can be used to  construct fault-tolerant data structures for shortest paths and even for NP-hard problems like k-Path and  k-Clique.<\/p>\n\n\n\n<p>The talk is based on joined work with Davide Bil\u00f2, Keerti Choudhary, Sarel Cohen, and Tobias Friedrich  that appeared at AAAI 2025.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Date: 08 May 2025Time: 11:45 &#8211; 12:45Location: Forschungslabor 3 (sofa room) Speaker: Martin SchirneckTitle: Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks Abstract:This talk is about&#46;&#46;&#46;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-29","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/posts\/29","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=29"}],"version-history":[{"count":4,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/posts\/29\/revisions"}],"predecessor-version":[{"id":33,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/posts\/29\/revisions\/33"}],"wp:attachment":[{"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=29"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=29"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=29"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}