Copertina

Minor Containment and Disjoint Paths in almost-linear time

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Korhonen, Tuukka, Pilipczuk, Michał, Stamoulis, Giannos
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Combinatorics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
di: Pilipczuk, Michał, et al.
Pubblicazione: (2025)

Faster diameter computation in graphs of bounded Euler genus
di: Kluk, Kacper, et al.
Pubblicazione: (2025)

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

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

Elementary first-order model checking for sparse graphs
di: Gajarský, Jakub, et al.
Pubblicazione: (2024)

Coarse Balanced Separators in Fat-Minor-Free Graphs
di: Bonnet, Édouard, et al.
Pubblicazione: (2026)

On the Two Paths Theorem and the Two Disjoint Paths Problem
di: Humeau, Samuel, et al.
Pubblicazione: (2025)

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

Dynamic Treewidth in Logarithmic Time
di: Korhonen, Tuukka
Pubblicazione: (2025)

Graph classes through the lens of logic
di: Pilipczuk, Michał
Pubblicazione: (2025)

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

Connectivity augmentation is fixed-parameter tractable
di: Korhonen, Tuukka, et al.
Pubblicazione: (2026)

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

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
di: Marx, Dániel, et al.
Pubblicazione: (2026)

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
di: Chudnovsky, Maria, et al.
Pubblicazione: (2024)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
di: Włodarczyk, Michał
Pubblicazione: (2024)

Variants of Merge-Width and Applications
di: Drabik, Karolina, et al.
Pubblicazione: (2026)

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
di: Golovach, Petr A., et al.
Pubblicazione: (2022)

Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm
di: Biedl, Therese
Pubblicazione: (2025)

Branch-width of represented matroids in matrix multiplication time
di: Choi, Mujin, et al.
Pubblicazione: (2026)

Snakes and Ladders: a Treewidth Story
di: Chaplick, Steven, et al.
Pubblicazione: (2023)

Paths and Intersections: Exact Emulators for Planar Graphs
di: Li, George Z., et al.
Pubblicazione: (2025)

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

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

On Integer Programs That Look Like Paths
di: Briański, Marcin, et al.
Pubblicazione: (2025)

Dynamic Meta-Kernelization
di: Bertram, Christian, et al.
Pubblicazione: (2025)

Optimization with pattern-avoiding input
di: Berendsohn, Benjamin Aram, et al.
Pubblicazione: (2023)

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
di: Bodwin, Greg, et al.
Pubblicazione: (2023)

Revisiting Directed Disjoint Paths on tournaments (and relatives)
di: Gomes, Guilherme C. M., et al.
Pubblicazione: (2025)

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
di: Majewski, Konrad, et al.
Pubblicazione: (2022)

Induced Minors and Coarse Tree Decompositions
di: Chudnovsky, Maria, et al.
Pubblicazione: (2026)

Cover time of random subgraphs of the hypercube
di: Cooper, Colin, et al.
Pubblicazione: (2025)

Treewidth of the $n \times n$ toroidal grid
di: Gima, Tatsuya, et al.
Pubblicazione: (2026)

A linear-time algorithm for $(1+ε)Δ$-edge-coloring
di: Bernshteyn, Anton, et al.
Pubblicazione: (2024)

Characterizing and Testing Principal Minor Equivalence of Matrices
di: Chatterjee, Abhranil, et al.
Pubblicazione: (2024)

On Detecting $H$-Induced Minors for Small $H$
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2026)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
di: Lokshtanov, Daniel, et al.
Pubblicazione: (2026)

Enumerating all minimal hitting sets in polynomial total time
di: Wild, Marcel
Pubblicazione: (2023)

Improved space-time tradeoff for TSP via extremal set systems
di: Dallant, Justin, et al.
Pubblicazione: (2026)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
di: Bentert, Matthias, et al.
Pubblicazione: (2024)