How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Huber, Michael Kiran
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms 05C85, 68Q25 G.2.2; F.2.2
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
von: Morse, Gregory, et al.
Veröffentlicht: (2026)

Competitive Query Minimization for Stable Matching with One-Sided Uncertainty
von: Bampis, Evripidis, et al.
Veröffentlicht: (2024)

Shortest two disjoint paths in conservative graphs
von: Schlotter, Ildikó
Veröffentlicht: (2023)

Overlapping Biclustering
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Simple minimally unsatisfiable subsets of 2-CNFs
von: Kullmann, Oliver, et al.
Veröffentlicht: (2026)

Steiner Tree Parameterized by Multiway Cut and Even Less
von: Jansen, Bart M. P., et al.
Veröffentlicht: (2024)

Experimental algorithms for the dualization problem
von: Mezzini, Mauro, et al.
Veröffentlicht: (2025)

ARRIVAL: Recursive Framework & $\ell_1$-Contraction
von: Haslebacher, Sebastian
Veröffentlicht: (2025)

O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold
von: Bell, Tolson, et al.
Veröffentlicht: (2024)

On Solving Simple Curved Nonograms
von: Löffler, Maarten, et al.
Veröffentlicht: (2025)

Maximum Matchings in Geometric Intersection Graphs
von: Bonnet, Édouard, et al.
Veröffentlicht: (2019)

Faster shortest-path algorithms using the acyclic-connected tree
von: Stefansson, Elis, et al.
Veröffentlicht: (2025)

Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing
von: Krishnaswamy, Ravishankar, et al.
Veröffentlicht: (2014)

On (In)approximability of MaxMin Independent Set Reconfiguration
von: Hoang, Hung P., et al.
Veröffentlicht: (2026)

A New Temporal Interpretation of Cluster Editing
von: Bocci, Cristiano, et al.
Veröffentlicht: (2022)

Interval Graphs are Reconstructible
von: Heinrich, Irene, et al.
Veröffentlicht: (2025)

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
von: Bonnet, Édouard, et al.
Veröffentlicht: (2026)

Fully Dynamic Maintenance of Loop Nesting Forests in Reducible Flow Graphs
von: Morse, Gregory, et al.
Veröffentlicht: (2026)

On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)
von: DasGupta, Bhaskar, et al.
Veröffentlicht: (2026)

A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
von: Bergougnoux, Benjamin, et al.
Veröffentlicht: (2025)

Optimal non-adaptive algorithm for edge estimation
von: Bishnu, Arijit, et al.
Veröffentlicht: (2025)

Traffic-Oblivious Multi-Commodity Flow Network Design
von: Chimani, Markus, et al.
Veröffentlicht: (2025)

Searching in trees with monotonic query times
von: Dereniowski, Dariusz, et al.
Veröffentlicht: (2024)

On the twin-width of near-regular graphs
von: Heinrich, Irene, et al.
Veröffentlicht: (2025)

On the Integrality Gap of Directed Steiner Tree LPs with Relatively Integral Solutions
von: Laekhanukit, Bundit
Veröffentlicht: (2024)

Decline and Fall of the ICALP 2008 Modular Decomposition algorithm
von: Atherton, William, et al.
Veröffentlicht: (2024)

Minimum-cost paths for electric cars
von: Dorfman, Dani, et al.
Veröffentlicht: (2024)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
von: Heimann, Sophia, et al.
Veröffentlicht: (2024)

Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics
von: An, Hyung-Chan, et al.
Veröffentlicht: (2025)

Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint
von: Filmus, Yuval, et al.
Veröffentlicht: (2024)

Extending Exact Integrality Gap Computations for the Metric TSP
von: Cook, William, et al.
Veröffentlicht: (2026)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
von: Heimann, Sophia, et al.
Veröffentlicht: (2026)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
von: Grochow, Joshua A., et al.
Veröffentlicht: (2025)

Finding Diverse Minimum s-t Cuts
von: de Berg, Mark, et al.
Veröffentlicht: (2023)

Answering Related Questions
von: Bonnet, Édouard
Veröffentlicht: (2025)

Coloring Hardness on Low Twin-Width Graphs
von: Bonnet, Édouard
Veröffentlicht: (2025)

A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm
von: Hougardy, Stefan, et al.
Veröffentlicht: (2025)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
von: Heimann, Sophia, et al.
Veröffentlicht: (2025)

A Constant-factor Approximation for Weighted Bond Cover
von: Kim, Eun Jung, et al.
Veröffentlicht: (2021)

On Solving Reachability in Grid Digraphs using a Psuedoseparator
von: Jain, Rahul, et al.
Veröffentlicht: (2019)