Personal tools
You are here: Home CG seminar 2018 Efficient Algorithms for Finding Vulnerabilities in Communication Networks
« October 2018 »
October
SuMoTuWeThFrSa
123456
78910111213
14151617181920
21222324252627
28293031
Log in


Forgot your password?
 

Efficient Algorithms for Finding Vulnerabilities in Communication Networks

Wednesday, December 20th, 2017, 16:10

Schreiber 309

underline

Efficient Algorithms for Finding Vulnerabilities in Communication Networks

Yael Golan, TAU

Abstract:

Many communication networks exist around the world. Many of our daily activities are based on them, from talking on the phone, watching television, all the way to surfing the Internet. A wired network can be modeled as a graph. The stations, or switchboards, are the graph vertices, and the wires that connect the stations are the edges. A wired network can be damaged by extreme weather conditions (like wind storms, hailstones, etc.), or by a bomb, during a war, or by other means of attack, such as an electro-magnetic pulse (EMP).
 
In this lecture we consider communication networks as straight-edge graphs embedded in the plane, and an attack on the network as a region that destroys all the edges that intersect it. We want to find the placement of an attack of some given shape where it intersects the maximum number of edges of the graph.
 
We review several combinations of different types of graphs and attacks. Three of the problems that are discussed were already solved in "Assessing the vulnerability of the fiber infrastructure to disasters" by S. Neumayer, G. Zussman, R. Cohen, and E. Modiano. All of our algorithms significantly improve the results of this preceding work.
Document Actions