Buchumschlag

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bentert, Matthias, Fomin, Fedor V., Golovach, Petr A.
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
von: Bentert, Matthias, et al.
Veröffentlicht: (2026)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

When does FTP become FPT?
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Fault-Tolerant Matroid Bases
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
von: Fomin, Fedor V., et al.
Veröffentlicht: (2025)

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
von: Chitnis, Rajesh, et al.
Veröffentlicht: (2024)

Algorithmic Extensions of Dirac's Theorem
von: Fomin, Fedor V., et al.
Veröffentlicht: (2020)

Packing Short Cycles
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Fixed-Parameter Tractability of Hedge Cut
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Stability in Graphs with Matroid Constraints
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Edge Clique Partition and Cover Beyond Independence
von: Fomin, Fedor V., et al.
Veröffentlicht: (2025)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Computing Tree Decompositions with Small Independence Number
von: Dallard, Clément, et al.
Veröffentlicht: (2022)

H-Planarity and Parametric Extensions: when Modulators Act Globally
von: Fomin, Fedor V., et al.
Veröffentlicht: (2025)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
von: Pilipczuk, Michał, et al.
Veröffentlicht: (2025)

Parameterized Geometric Graph Modification with Disk Scaling
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Hybrid k-Clustering: Blending k-Median and k-Center
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality
von: Fomin, Fedor V., et al.
Veröffentlicht: (2026)

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
von: Choudhary, Keerti, et al.
Veröffentlicht: (2025)

Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
von: Bai, Tian, et al.
Veröffentlicht: (2026)

Detecting Disjoint Shortest Paths in Linear Time and More
von: Akmal, Shyan, et al.
Veröffentlicht: (2024)

Line Cover and Related Problems
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Polynomial Kernels for Spanning Tree with Diversity Requirements
von: Golovach, Petr A., et al.
Veröffentlicht: (2026)

Covering Approximate Shortest Paths with DAGs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Cuts in Graphs with Matroid Constraints
von: Banik, Aritra, et al.
Veröffentlicht: (2024)

Planar Network Diversion
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Hardness of Approximation for Shortest Path with Vector Costs
von: Carlson, Charlie, et al.
Veröffentlicht: (2025)

On Incremental Approximate Shortest Paths in Directed Graphs
von: Górkiewicz, Adam, et al.
Veröffentlicht: (2025)

Breaking the Bellman-Ford Shortest-Path Bound
von: Elmasry, Amr
Veröffentlicht: (2024)

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
von: Wlodarczyk, Michal
Veröffentlicht: (2023)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
von: Włodarczyk, Michał
Veröffentlicht: (2024)

Distributed Model Checking on Graphs of Bounded Treedepth
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Tight Sampling Bounds for Eigenvalue Approximation
von: Swartworth, William, et al.
Veröffentlicht: (2024)

What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing
von: Blin, Lélia, et al.
Veröffentlicht: (2024)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
von: Ashvinkumar, Vikrant, et al.
Veröffentlicht: (2024)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
von: Dory, Michal, et al.
Veröffentlicht: (2022)