Monitoring the edges of a graph using distances

DOI10.1007/978-3-030-39219-2_3zbMath1452.68136arXiv2011.00029OpenAlexW3001163125MaRDI QIDQ5896103

Ralf Klasing, Mirka Miller, Florent Foucaud, Joseph F. Ryan, Shih-Shun Kao

Publication date: 21 July 2020

Published in: Discrete Applied Mathematics, Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2011.00029

zbMATH Keywords

identificationcomplexityapproximationboundsshortest pathsdistance-edge-monitoring set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12)

Related Items

Monitoring edge-geodetic sets: hardness and graph products ⋮ Monitoring the edges of a graph using distances with given girth ⋮ Monitoring edge-geodetic sets in graphs ⋮ On the distance-edge-monitoring numbers of graphs ⋮ Erdös-Gallai-type problems for distance-edge-monitoring numbers ⋮ Monitoring the edges of a graph using distances

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• The (weighted) metric dimension of graphs: hard and easy cases
• On the parameterized complexity of the edge monitoring problem
• Network verification via routing table queries
• The strong metric dimension of graphs and digraphs
• Discovery of network properties with all-shortest-paths queries
• Approximation algorithms for combinatorial problems
• Uniquely identifying the edges of a graph: the edge metric dimension
• Mixed metric dimension of graphs
• Exploring networks with traceroute-like probes: Theory and simulations
• Strong edge geodetic problem in networks
• Tight lower bounds for certain parameterized NP-hard problems
• The metric dimension for resolving several objects
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Analytical approach to parallel repetition
• On Metric Generators of Graphs
• Monitoring the edges of a graph using distances
• Parameterized Complexity of Geodetic Set

This page was built for publication: Monitoring the edges of a graph using distances