Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity

DOI10.1007/978-3-031-52213-0_3MaRDI QIDQ6547818zbMATH OpenFDO

Authors Florent Foucaud, Pierre-Marie Marcille, Zin Mar Myint, R. B. Sandeep, Sagnik Sen, S. Taruni

Publication date 31 May 2024

Full work available at URL https://doi.org/10.1007/978-3-031-52213-0_3

zbMATH Keywords

\(k\)-clique sumchromatic numbercomputational complexitygeodetic setgirthmonitoring edge geodetic setsubdivisions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Algorithms in computer science (68Wxx)

Cites work

• Algorithms and complexity for geodetic sets on partial grids
• Complete graph minors and the graph minor structure theorem
• Discovery of network properties with all-shortest-paths queries
• Edge geodetic number of a graph
• Edge-Deletion Problems
• Exploring networks with traceroute-like probes: Theory and simulations
• Graph minor theory
• Graph minors. XVII: Taming a vortex
• Graph minors. XX: Wagner's conjecture
• scientific article; zbMATH DE number 1933222 (Why is no real title available?)
• scientific article; zbMATH DE number 7765365 (Why is no real title available?)
• Monitoring edge-geodetic sets in graphs
• Monitoring edge-geodetic sets: hardness and graph products
• Network verification via routing table queries
• On the approximation hardness of geodetic set and its variants
• On The Edge Geodetic Number Of A Graph
• On the geodetic number of a graph
• Parameterized complexity of geodetic set
• Some remarks on the geodetic number of a graph
• Strong edge geodetic problem in networks
• Strong geodetic number of complete bipartite graphs and of graphs with specified diameter
• The geodetic number of a graph

Cited in

(9)

• Fault-tolerance in distance-edge-monitoring sets
• Linear programming of monitoring the links of a fractional weighted network using distance
• Nordhaus-Gaddum-type results for monitoring edge-geodetic number of graphs
• Distance-based (and path-based) covering problems for graphs of given cyclomatic number
• Bounds and extremal graphs for monitoring edge-geodetic sets in graphs
• Monitoring arc-geodetic sets of oriented graphs
• Characterizing optimal monitoring edge-geodetic sets for some structured graph classes
• Algorithms and complexity for monitoring edge-geodetic sets in graphs
• On the (in)approximability of the monitoring edge geodetic set problem

This page was built for publication: Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity

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