Parameterized Complexity of Geodetic Set
From MaRDI portal
Publication:6089667
DOI10.4230/LIPICS.IPEC.2020.20OpenAlexW3116288092MaRDI QIDQ6089667FDOQ6089667
Authors: Leon Kellerhals, Tomohiro Koana 
Publication date: 13 November 2023
Full work available at URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.20
data reductionshortest pathsinteger linear programmingtree-likenessNP-hard graph problemsparameter hierarchy
Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Linear time solvable optimization problems on graphs of bounded clique-width
- Integer Programming with a Fixed Number of Variables
- On the Relationship Between Clique-Width and Treewidth
- Sparsity. Graphs, structures, and algorithms
- Some remarks on the geodetic number of a graph
- Hull number: \(P_5\)-free graphs and reduction rules
- The (weighted) metric dimension of graphs: hard and easy cases
- A survey of the algorithmic aspects of modular decomposition
- On the geodetic number and related metric sets in Cartesian product graphs
- Metric dimension parameterized by max leaf number
- Hardness and approximation for the geodetic set problem in some graph classes
- Metric Dimension of Bounded Tree-length Graphs
- Computational Complexity of Geodetic Set
- Notes on complexity of packing coloring
- On the hardness of finding the geodetic number of a subcubic graph
- The geodetic hull number is hard for chordal graphs
- On the parameterized complexity of the geodesic hull number
- Title not available (Why is that?)
Cited In (9)
- On graphs coverable by \({k}\) shortest paths
- Geometric complexity of some location problems
- Well-partitioned chordal graphs
- Algorithms and complexity for geodetic sets on partial grids
- Title not available (Why is that?)
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Length-bounded cuts: proper interval graphs and structural parameters
- Block decomposition approach to compute a minimum geodetic set
This page was built for publication: Parameterized Complexity of Geodetic Set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6089667)
