Cover Image

Detecting Disjoint Shortest Paths in Linear Time and More

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Akmal, Shyan, Williams, Virginia Vassilevska, Wein, Nicole
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An Enumerative Perspective on Connectivity
by: Akmal, Shyan
Published: (2023)

Graph Coloring Below Guarantees via Co-Triangle Packing
by: Akmal, Shyan, et al.
Published: (2025)

Node-Weighted Triangles: Faster and Simpler
by: Akmal, Shyan, et al.
Published: (2026)

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
by: Abboud, Amir, et al.
Published: (2025)

On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2023)

Tightest Admissible Shortest Path
by: Weiss, Eyal, et al.
Published: (2023)

Shortest Paths in Multimode Graphs
by: Kirkpatrick, Yael, et al.
Published: (2025)

A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
by: Weiss, Eyal, et al.
Published: (2022)

On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints
by: Bandopadhyay, Susobhan, et al.
Published: (2026)

A Sublinear Algorithm for Approximate Shortest Paths in Large Networks
by: Basu, Sabyasachi, et al.
Published: (2024)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2022)

Determining Implication of Fixed Matrix Prenex Normal Forms Can Be Decided in Linear Time
by: Wang, Adam
Published: (2025)

Parameterized Complexity of Path Set Packing
by: Aravind, N. R., et al.
Published: (2022)

Path Contraction Faster than $2^n$
by: Agrawal, Akanksha, et al.
Published: (2025)

Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
by: Fomin, Fedor V., et al.
Published: (2024)

Tight Paths and Tight Pairs in Weighted Directed Graphs
by: Balcázar, José Luis
Published: (2025)

Efficient Online Sensitivity Analysis For The Injective Bottleneck Path Problem
by: Kaymakov, Kirill V., et al.
Published: (2024)

Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network
by: Manna, Bubai, et al.
Published: (2024)

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

On the Relationship Between Several Variants of the Linear Hashing Conjecture
by: Westover, Alek
Published: (2023)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
by: Bourneuf, Romain, et al.
Published: (2025)

Generalizing Roberts' characterization of unit interval graphs
by: Martínez, Virginia Ardévol, et al.
Published: (2024)

All-Hops Shortest Paths
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

Triangle Detection in H-Free Graphs
by: Abboud, Amir, et al.
Published: (2025)

Hypergraph Connectivity Augmentation in Strongly Polynomial Time
by: Bérczi, Kristóf, et al.
Published: (2024)

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

Arborescences and Shortest Path Trees when Colors Matter
by: Ardra, P. S., et al.
Published: (2024)

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2024)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
by: Ghanbari, Babak, et al.
Published: (2026)

DRESS and the WL Hierarchy: Climbing One Deletion at a Time
by: Velilla, Eduar Castrillo
Published: (2026)

Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
by: Marin, Malory
Published: (2025)

Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
by: Soulignac, Francisco J.
Published: (2025)

Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches
by: Jordon, Addie, et al.
Published: (2025)

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

Double-Ended Palindromic Trees in Linear Time
by: Wang, Qisheng, et al.
Published: (2022)

Space-Efficient Hierholzer: Eulerian Cycles in $\mathrm{O}(m)$ Time and $\mathrm{O}(n)$ Space
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)

Fanciful Figurines flip Free Flood-It -- Polynomial-Time Miniature Painting on Co-gem-free Graphs
by: Rosenke, Christian, et al.
Published: (2026)

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

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