Cover Image

Connectivity augmentation is fixed-parameter tractable

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Korhonen, Tuukka, Thorup, Mikkel
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Branch-width of connectivity functions is fixed-parameter tractable
by: Korhonen, Tuukka, et al.
Published: (2026)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
by: Korhonen, Tuukka
Published: (2024)

Dynamic Treewidth in Logarithmic Time
by: Korhonen, Tuukka
Published: (2025)

Instance-Optimality in PageRank Computation
by: Thorup, Mikkel, et al.
Published: (2025)

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
by: Jin, Wenyu, et al.
Published: (2024)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
by: Huang, Shang-En, et al.
Published: (2016)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
by: Goranci, Gramoz, et al.
Published: (2023)

Pivot based correlation clustering in the presence of good clusters
by: Lolck, David Rasmussen, et al.
Published: (2026)

Minor Containment and Disjoint Paths in almost-linear time
by: Korhonen, Tuukka, et al.
Published: (2024)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
by: Korhonen, Tuukka, et al.
Published: (2024)

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
by: Bodlaender, Hans L., et al.
Published: (2025)

A Faster Algorithm for Constrained Correlation Clustering
by: Fischer, Nick, et al.
Published: (2025)

PageRank Centrality in Directed Graphs with Bounded In-Degree
by: Thorup, Mikkel, et al.
Published: (2025)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
by: Narayanan, Shyam, et al.
Published: (2024)

Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
by: Hatzel, Meike, et al.
Published: (2022)

Dynamic Meta-Kernelization
by: Bertram, Christian, et al.
Published: (2025)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
by: Kacham, Praneeth, et al.
Published: (2023)

Separator Theorem for Minor-Free Graphs in Linear Time
by: Bonnet, Édouard, et al.
Published: (2025)

Estimating Random-Walk Probabilities in Directed Graphs
by: Bertram, Christian, et al.
Published: (2025)

Faster All-Pairs Optimal Electric Car Routing
by: Dorfman, Dani, et al.
Published: (2025)

Fixed-Parameter Tractability of Hedge Cut
by: Fomin, Fedor V., et al.
Published: (2024)

Fast Similarity Sketching
by: Dahlgaard, Søren, et al.
Published: (2017)

Hashing for Sampling-Based Estimation
by: Aamand, Anders, et al.
Published: (2024)

Combinatorial Correlation Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Computing Tree Decompositions with Small Independence Number
by: Dallard, Clément, et al.
Published: (2022)

Stability in Graphs with Matroid Constraints
by: Fomin, Fedor V., et al.
Published: (2024)

Computing diverse pair of solutions for tractable SAT
by: Gima, Tatsuya, et al.
Published: (2024)

Better coloring of 3-colorable graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2024)

Packing Short Cycles
by: Bentert, Matthias, et al.
Published: (2024)

ExpoSort: Breaking the quasi-polynomial-time barrier for reluctant sorting
by: Abrahamsen, Mikkel
Published: (2024)

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
by: Fischer, David, et al.
Published: (2022)

Solving the Correlation Cluster LP in Sublinear Time
by: Cao, Nairen, et al.
Published: (2025)

Static to Dynamic Correlation Clustering
by: Cao, Nairen, et al.
Published: (2025)

Improved fixed-parameter bounds for Min-Sum-Radii and Diameters $k$-clustering and their fair variants
by: Banerjee, Sandip, et al.
Published: (2025)

The tractability landscape of diffusion alignment: regularization, rewards, and computational primitives
by: Moitra, Ankur, et al.
Published: (2026)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
by: Fomin, Fedor V., et al.
Published: (2025)

Minimum-cost paths for electric cars
by: Dorfman, Dani, et al.
Published: (2024)

A short note about the learning-augmented secretary problem
by: Choo, Davin, et al.
Published: (2024)

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
by: Bonnet, Édouard, et al.
Published: (2023)

Positive bias makes tensor-network contraction tractable
by: Jiang, Jiaqing, et al.
Published: (2024)