On graphs coverable by k shortest paths

DOI10.1137/23M1564511MaRDI QIDQ6561322FDOQ6561322

Maël Dumas, Florent Foucaud, Anthony Perez, Ioan Todinca

Publication date: 25 June 2024

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

graph theoryshortest pathsparameterized algorithmscovering problems

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Cites Work

• Exact exponential algorithms.
• Graph minors. XIII: The disjoint paths problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Parameterized Algorithms
• A game of cops and robbers
• The disjoint shortest paths problem
• Strong edge geodetic problem in networks
• The isometric path number of a graph
• On the isometric path partition problem
• Isometric-path numbers of block graphs
• Path covering problems and testing of printed circuits
• Parameterized Complexity of Geodetic Set
• Strong geodetic problem in networks
• Structurally parameterized \(d\)-scattered set
• An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs
• On the approximation hardness of geodetic set and its variants
• Parameterizing path partitions
• Title not available (Why is that?)
• Complexity and algorithms for isometric path cover on chordal graphs and beyond

Cited In (1)

• Parameterizing path partitions

This page was built for publication: On graphs coverable by \({k}\) shortest paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6561322)