Designing virus-resistant networks: A game-formation approach

Forming, in a decentralized fashion, an optimal network topology while balancing multiple, possibly conflicting objectives like cost, high performance, security and resiliency to viruses is a challenging endeavor. In this paper, we take a game-formation approach to network design where each player, for instance an autonomous system in the...

ILIGRA: An Efficient Inverse Line Graph Algorithm

This paper presents a new and efficient algorithm, ILIGRA, for inverse line graph construction. Given a line graph H, ILIGRA constructs its root graph G with the time complexity being linear in the number of nodes in H. If ILIGRA does not know whether the given graph H is a line graph, it firstly assumes that H is a line graph and starts its...

Finding Critical Regions and Region-Disjoint Paths in a Network

Due to their importance to society, communication networks should be built and operated to withstand failures.However, cost considerations make network providers less inclined to take robustness measures against failures that are unlikely to manifest, like several failures coinciding simultaneously in different geographic regions of their...

Fiedler’s Clustering on m?dimensional Lattice Graphs

We consider the partitioning of m-dimensional lattice graphs using Fiedler’s approach [1], that requires the determination of the eigenvector belonging to the second smallest eigenvalue of the Laplacian. We examine the general m-dimensional lattice and, in particular, the special cases: the 1-dimensional path graph PN and the 2-dimensional...