Personal tools
You are here: Home CG seminar 2018 Efficient Algorithms for Finding Vulnerabilities in Communication Networks
« August 2018 »
August
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
262728293031
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