Personal tools
You are here: Home CG seminar 2018 Efficient Algorithms for Finding Vulnerabilities in Communication Networks
« December 2017 »
December
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
31
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