Search

Harmful Internet hijacking incidents put in evidence how fragile interdomain routing is. In particular, the Border Gateway Protocol (BGP), which is used to exchange routing information between Internet entities, called Autonomous Systems (ASes), proved to be prone to attacks launched by a single malicious AS. Recent research contributions pointed out that even S-BGP, the secure variant of BGP that is being deployed, is not fully able to blunt traffic attraction attacks. Given a traffic flow between two ASes, we study how difficult it is for a malicious AS to devise a strategy for hijacking or intercepting that flow. The goal of the attack is to attract a traffic flow towards the malicious AS. While in the hijacking attack connectivity between the endpoints of a flow can be disrupted, in the interception attack connectivity must be maintained. We show that this problem marks a sharp difference between BGP and S-BGP. Namely, while it is solvable, under reasonable assumptions, in polynomial time for the type of attacks that are usually performed in BGP, it is NP-hard for S-BGP. Our study has several by-products. E.g., we solve a problem left open in the literature, stating when performing a hijacking in S-BGP is equivalent to performing an interception. [ABSTRACT FROM AUTHOR]

In this paper we settle the computational complexity of two open problems related to the extension of the notion of level planarity to surfaces different from the plane. Namely, we show that the problems of testing the existence of a level embedding of a level graph on the surface of the rolling cylinder or on the surface of the torus, respectively known by the name of Cyclic Level Planarity and Torus Level Planarity , are polynomial-time solvable. Moreover, we show a complexity dichotomy for testing the Simultaneous Level Planarity of a set of level graphs, with respect to both the number of level graphs and the number of levels. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we analyze the relationships among different planar embeddings of the same graph and study how two planar embeddings can be morphed one into the other with the minimum number of elementary changes, while preserving the mental map of the user. We call this problem Topological Morphing, in analogy with the well-known Geometric Morphing problem, in which it is studied how two planar drawings can be morphed one into the other with the minimum number of elementary changes. First, we define two operations, called flip and skip, describing natural transformations of a graph embedding that preserve the mental map of the user. Then, we study the problem of performing a morph while minimizing the number of these operations. We show that the Topological Morphing problem is NP-hard for biconnected planar graphs, we give polynomial-time algorithms for some restricted versions of the problem, and, based on such polynomial-time algorithms, we give a fixed-parameter tractable algorithm for the general case. [Copyright &y& Elsevier]