Imagen de Portada

From Hop Reduction to Sparsification for Negative Length Shortest Paths

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Quanrud, Kent, Tajkhorshid, Navid
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms 05C85
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes
por: Kokai, Toranosuke, et al.
Publicado: (2025)

On the Complexity of the Bilevel Shortest Path Problem
por: Henke, Dorothee, et al.
Publicado: (2024)

$t$-sails and sparse hereditary classes of unbounded tree-width
por: Cocks, Daniel
Publicado: (2023)

Tight Bounds for Feedback Vertex Set Parameterized by Clique-width
por: Bojikian, Narek, et al.
Publicado: (2025)

Tight Bounds for some Classical Problems Parameterized by Cutwidth
por: Bojikian, Narek, et al.
Publicado: (2025)

A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees
por: Jaffke, Lars, et al.
Publicado: (2025)

Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width
por: Bojikian, Narek, et al.
Publicado: (2024)

A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
por: Bojikian, Narek, et al.
Publicado: (2023)

Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
por: Baste, Julien, et al.
Publicado: (2019)

The Complexity of Distance-$r$ Dominating Set Reconfiguration
por: Banerjee, Niranka, et al.
Publicado: (2023)

A simple quadratic kernel for Token Jumping on surfaces
por: Cranston, Daniel W., et al.
Publicado: (2024)

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
por: Oum, Sang-il, et al.
Publicado: (2026)

Approximating Directed Connectivity in Almost-Linear Time
por: Quanrud, Kent
Publicado: (2025)

Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting
por: Nasre, Meghana, et al.
Publicado: (2023)

On 3-Coloring of $(2P_4,C_5)$-Free Graphs
por: Jelínek, Vít, et al.
Publicado: (2020)

On $γ$-Contraction and $β$-Contraction: A Unified Framework for Colour-Preserving Graph Reduction
por: Onofri, Elia
Publicado: (2024)

Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-shortest Induced Paths
por: Chiu, Yung-Chung, et al.
Publicado: (2021)

Shortest two disjoint paths in conservative graphs
por: Schlotter, Ildikó
Publicado: (2023)

A practical algorithm for 2-admissibility
por: Awofeso, Christine, et al.
Publicado: (2025)

A Simple 2-Approximation for Maximum-Leaf Spanning Tree
por: Liao, I-Cheng, et al.
Publicado: (2023)

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

Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time
por: Agrawal, Akanksha, et al.
Publicado: (2024)

Finding Diverse Solutions Parameterized by Cliquewidth
por: Drabik, Karolina, et al.
Publicado: (2024)

Designing Capacitated Subnetworks for Shortest Path Routing
por: Chimani, Markus, et al.
Publicado: (2026)

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

Optimal Path Partitions in Subcubic and Almost-subcubic Graphs
por: Masařík, Tomáš, et al.
Publicado: (2026)

On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
por: Munaro, Andrea, et al.
Publicado: (2022)

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$
por: Bonnet, Édouard, et al.
Publicado: (2023)

Improved Outerplanarity Bounds for Planar Graphs
por: Biedl, Therese, et al.
Publicado: (2024)

Steiner Tree Parameterized by Multiway Cut and Even Less
por: Jansen, Bart M. P., et al.
Publicado: (2024)

Finding Diverse Minimum s-t Cuts
por: de Berg, Mark, et al.
Publicado: (2023)

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
por: Gartland, Peter, et al.
Publicado: (2023)

Tree independence number V. Walls and claws
por: Chudnovsky, Maria, et al.
Publicado: (2025)

Faster negative length shortest paths by bootstrapping hop reducers
por: Huang, Yufan, et al.
Publicado: (2025)

Faster single-source shortest paths with negative real weights via proper hop distance
por: Huang, Yufan, et al.
Publicado: (2024)

Shortcutting for Negative-Weight Shortest Path
por: Li, George Z., et al.
Publicado: (2025)

On the joint embedding property for cographs and trees
por: Carter, Daniel
Publicado: (2024)

Reconfiguring homomorphisms to reflexive graphs via a simple reduction
por: Mühlenthaler, Moritz, et al.
Publicado: (2024)

Excluding a Forest Induced Minor
por: Bonnet, Édouard, et al.
Publicado: (2025)

Zero-free regions of partition functions with applications to algorithms and graph limits
por: Regts, Guus
Publicado: (2015)