COMPUTER SCIENCE DEPARTMENT
COLLEGE OF STATEN ISLAND
CITY UNIVERSITY OF NEW YORK
Dr. Louis Petingi
Research: Network Reliability and Extremal Graph Theory
Network Reliability: Network components (nodes and communication links) may be subject to random failures. The reliability of a network is the probability that the network withstands these failures. A widely used probabilistic model is the one that links fail independently with known probabilities, and where the nodes are always operative. Given a network with terminal nodes K, the Kterminal Reliability of this network, is the probability that the operating links permit the terminal nodes to communicate between each other (i.e. there exists a path of operative links between every pair of nodes of K).
Recently, we generalized this measure by restricting the paths length between every pair of K to be at most a given upper bound D. This parameter, called the Diameterconstrained Kterminal Reliability, is the probability that the network terminal nodes meet certain delay constraints.
Extremal Graph Theory: Characterize among competing topologies with equal number of nodes and edges, the ones that maximize or minimize graph theoretic indexes (e.g. number of spanning trees, connectivity, etc.)
General Information
