Imagen de Portada

On the Two Paths Theorem and the Two Disjoint Paths Problem

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Humeau, Samuel, Pous, Damien
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms Combinatorics
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

Testing H-freeness on sparse graphs, the case of bounded expansion
por: Humeau, Samuel, et al.
Publicado: (2025)

An Algebraic Approach to the Longest Path Problem
por: Khazali, Omar Al -
Publicado: (2023)

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
por: Choudhary, Keerti, et al.
Publicado: (2025)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
por: Chitnis, Rajesh, et al.
Publicado: (2024)

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

Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz--Parisi Potential
por: Koehler, Frederic, et al.
Publicado: (2025)

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

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

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
por: Leake, Jonathan, et al.
Publicado: (2025)

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

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
por: Bhaskar, Umang, et al.
Publicado: (2025)

Parameterized Shortest Path Reconfiguration
por: Bousquet, Nicolas, et al.
Publicado: (2024)

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

Uncrossed Multiflows and Applications to Disjoint Paths
por: Chekuri, Chandra, et al.
Publicado: (2025)

Parameterized Maximum Node-Disjoint Paths
por: Lampis, Michael, et al.
Publicado: (2024)

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

Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond
por: Kobayashi, Yasuaki, et al.
Publicado: (2023)

A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices
por: Kano, Takumi, et al.
Publicado: (2026)

On the Enumeration of all Unique Paths of Recombining Trinomial Trees
por: Torres, Ethan, et al.
Publicado: (2025)

Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
por: von Bergen, Hanno, et al.
Publicado: (2026)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
por: Iwata, Satoru, et al.
Publicado: (2024)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
por: Deligkas, Argyrios, et al.
Publicado: (2025)

Paths and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances
por: Chen, Yu, et al.
Publicado: (2024)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
por: Bucić, Matija, et al.
Publicado: (2025)

Detecting Disjoint Shortest Paths in Linear Time and More
por: Akmal, Shyan, et al.
Publicado: (2024)

An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
por: Murakami, Hitoshi, et al.
Publicado: (2024)

Complexity and Algorithm for the Matching vertex-cutset Problem
por: Li, Hengzhe, et al.
Publicado: (2025)

Odd and Even Harder Problems on Cycle-Factors
por: Hörsch, Florian, et al.
Publicado: (2025)

Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
por: Haviv, Ishay
Publicado: (2022)

A Maximum Linear Arrangement Problem on Directed Graphs
por: DeVos, Matt, et al.
Publicado: (2018)

Complexity Gaps between Point and Interval Temporal Graphs for some Reachability Problems
por: Aubian, Guillaume, et al.
Publicado: (2025)

Optimising Cylindrical Algebraic Coverings for use in SMT by Solving a Set Covering Problem with Reasons
por: Babatunde, Abiola, et al.
Publicado: (2026)

Computing Hamiltonian Paths with Partial Order Restrictions
por: Beisegel, Jesse, et al.
Publicado: (2024)

The Steiner Path Aggregation Problem
por: Chen, Da Qi, et al.
Publicado: (2025)

On the Complexity of Secluded Path Problems
por: Hanaka, Tesshu, et al.
Publicado: (2026)

Zone Theorem for Arrangements in three dimensions
por: Saxena, Sanjeev
Publicado: (2020)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths
por: Beisegel, Jesse, et al.
Publicado: (2025)

The Steiner Shortest Path Tree Problem
por: Asher, Omer, et al.
Publicado: (2025)

Beer Path Problems in Temporal Graphs
por: D'Ascenzo, Andrea, et al.
Publicado: (2025)