Cover Image

On the Complexity of the Bilevel Shortest Path Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Henke, Dorothee, Wulf, Lasse
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms 90C17 (Primary) 05C85, 03D15 (Secondary) F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Shortest two disjoint paths in conservative graphs
by: Schlotter, Ildikó
Published: (2023)

Traffic-Oblivious Multi-Commodity Flow Network Design
by: Chimani, Markus, et al.
Published: (2025)

Simple Approximations for General Spanner Problems
by: Bökler, Fritz, et al.
Published: (2025)

Discounted Cuts: A Stackelberg Approach to Network Disruption
by: Drange, Pål Grønås, et al.
Published: (2025)

Tree-independence number VI. Thetas and pyramids
by: Chudnovsky, Maria, et al.
Published: (2025)

The Complexity Landscape of Two-Stage Robust Selection Problems with Budgeted Uncertainty
by: Goerigk, Marc, et al.
Published: (2026)

Exact Algorithms for MaxCut on Split Graphs
by: Lalovic, Marko
Published: (2024)

Exact Minimum Weight Spanners via Column Generation
by: Bökler, Fritz, et al.
Published: (2024)

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

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

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

Low Recourse Arborescence Forests Under Uniformly Random Arcs
by: Dahlmeier, J Niklas, et al.
Published: (2025)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
by: Morse, Gregory, et al.
Published: (2026)

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

TreePIR: Efficient Private Retrieval of Merkle Proofs via Tree Colorings with Fast Indexing and Zero Storage Overhead
by: Dau, Son Hoang, et al.
Published: (2022)

Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
by: Hommelsheim, Felix
Published: (2025)

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

Fully Dynamic Maintenance of Loop Nesting Forests in Reducible Flow Graphs
by: Morse, Gregory, et al.
Published: (2026)

Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
by: Alimi, Morteza, et al.
Published: (2025)

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

Cluster deletion and clique partitioning in graphs with bounded clique number
by: Galesi, Nicola, et al.
Published: (2025)

Solving the Graph Burning Problem for Large Graphs
by: Pereira, Felipe de Carvalho, et al.
Published: (2024)

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

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

Simultaneous recovery of a sparse topology and the admittance of an electrical network
by: Samperio, Álvaro
Published: (2023)

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

A $4/3$ Approximation for $2$-Vertex-Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2023)

Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
by: Bougeret, Marin, et al.
Published: (2024)

How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length
by: Huber, Michael Kiran
Published: (2024)

Kernelization dichotomies for hitting minors under structural parameterizations
by: Bougeret, Marin, et al.
Published: (2025)

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

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

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

Decline and Fall of the ICALP 2008 Modular Decomposition algorithm
by: Atherton, William, et al.
Published: (2024)

A $5/4$-Approximation for Two-Edge Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2024)

From Hop Reduction to Sparsification for Negative Length Shortest Paths
by: Quanrud, Kent, et al.
Published: (2025)

Conformality of Minimal Transversals of Maximal Cliques
by: Boros, Endre, et al.
Published: (2024)

A unified worst case for classical simplex and policy iteration pivot rules
by: Disser, Yann, et al.
Published: (2023)

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