Campus Event Calendar
Event Entry
What and Who
Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
Tuukka Korhonen
BARC, University of Copenhagen,
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 4 March 2025
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We present k^{O(k^2)} m time algorithms for various problems about decomposing a given graph by edge cuts or vertex separators of size less than k into parts that are "well-connected" with respect to cuts or separators of size less than k; here, m is the total number of vertices and edges of the graph. As an application of our results, we obtain for
every fixed k a linear-time algorithm for computing the k-edge-connected components of a given graph, solving a long-standing open problem. Our main technical result, from which the other results follow, is a k^{O(k^2)} m time algorithm for computing a so-called "k-lean tree decomposition" of a given graph.
The paper is available in arXiv at https://arxiv.org/abs/2411.02658.
Contact
Nidhi Rathi
+49 681 9325 1134
--email hidden
Virtual Meeting Details
Zoom
897 027 2575
passcode not visible
logged in users only
Nidhi Rathi, 02/18/2025 12:37 -- Created document.