Parameterized Complexity of Geodetic Set

DOI10.4230/lipics.ipec.2020.20OpenAlexW3116288092MaRDI QIDQ6089667

Leon Kellerhals, Tomohiro Koana

Publication date: 13 November 2023

Full work available at URL: https://doi.org/10.4230/LIPIcs.IPEC.2020.20

zbMATH Keywords

data reductionshortest pathsinteger linear programmingtree-likenessNP-hard graph problemsparameter hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

Length-bounded cuts: proper interval graphs and structural parameters ⋮ Well-partitioned chordal graphs ⋮ Monitoring the edges of a graph using distances ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity

Cites Work

• Unnamed Item
• Hull number: \(P_5\)-free graphs and reduction rules
• Sparsity. Graphs, structures, and algorithms
• A survey of the algorithmic aspects of modular decomposition
• The (weighted) metric dimension of graphs: hard and easy cases
• Hardness and approximation for the geodetic set problem in some graph classes
• Some remarks on the geodetic number of a graph
• On the geodetic number and related metric sets in Cartesian product graphs
• Notes on complexity of packing coloring
• On the hardness of finding the geodetic number of a subcubic graph
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the parameterized complexity of the geodesic hull number
• Metric Dimension Parameterized by Max Leaf Number
• Integer Programming with a Fixed Number of Variables
• Computational Complexity of Geodetic Set
• The Geodetic Hull Number is Hard for Chordal Graphs
• Metric Dimension of Bounded Tree-length Graphs
• On the Relationship Between Clique-Width and Treewidth

This page was built for publication: Parameterized Complexity of Geodetic Set