Network verification via routing table queries

DOI10.1016/j.jcss.2014.06.003zbMath1401.90052OpenAlexW1593732822MaRDI QIDQ743125

Ralf Klasing, Guido Proietti, Luciano Gualà, Davide Bilò, Evangelos Bampas, Guido Drovandi

Publication date: 22 September 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.06.003

zbMATH Keywords

computational complexityapproximation algorithmsgraph/network topologynetwork verification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Deterministic network models in operations research (90B10) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Related Items

Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ 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 ⋮ Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension ⋮ Monitoring the edges of a graph using distances ⋮ On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs ⋮ Tracking routes in communication networks ⋮ On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Discovery of network properties with all-shortest-paths queries
• Optimal query complexity bounds for finding graphs
• Approximation algorithms for connected dominating sets
• Exploring networks with traceroute-like probes: Theory and simulations
• Approximability of identifying codes and locating-dominating codes
• Reconstructing weighted graphs with minimal query complexity
• Landmarks in graphs
• On Moore Graphs with Diameters 2 and 3
• The Covert Set-Cover Problem with Application to Network Discovery
• Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
• Approximate Discovery of Random Graphs
• A Characterization of Block-Graphs