Network verification via routing table queries

DOI10.1016/j.jcss.2014.06.003zbMath1401.90052MaRDI 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 complexity; approximation algorithms; graph/network topology; network verification

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68M10: Network design and communication in computer systems

90B10: Deterministic network models in operations research

68M15: Reliability, testing and fault tolerance of networks and computer systems

Related Items

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

Uses Software

• Algorithm 447

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item