Publisher Summary This chapter focuses on the important practical and theoretical problem
of designing survivable communication networks, ie, communication networks that are still …

We further develop the study of testing graph properties as initiated by Goldreich,
Goldwasser and Ron. Whereas they view graphs as represented by their adjacency matrix …

What is the minimum number γ of edges to be added to a given graph G so that in the
resulting graph the edge-connectivity between every pair {u,v\} of its nodes is at least a …

Network survivability—the ability to maintain operation when one or a few network
components fail—is indispensable for present‐day networks. In this paper, we characterize …

A spanning tree in a graph is the smallest connected spanning subgraph. Given a graph,
how does one find the smallest (ie, least number of edges) 2-connected spanning subgraph …

A capacitated covering IP is an integer program of the form min {l_brace} ex {vert_bar} Ux
{ge} d, 0 {le} x {le} b, x {element_of} Z {sup+}{r_brace}, where all entries of c, U, and d are …

We present the first polynomial-time approximation algorithm for finding a minimum-cost
subgraph having at least a specified number of edges in each cut. This class of problems …

Property testing algorithms are" ultra"-efficient algorithms that decide whether a given object
(eg, a graph) has a certain property (eg, bipartiteness), or is significantly different from any …

Let a graph G=(V; E) denote the feasible links of a (proposed) communications network. An
edge e=(a; b) denotes the feasibility of adding a link between sites a and b. The weight of …

Let λ(\calN) denote the weight of a minimum cut in an edge-weighted undirected network
\calN, and n and m denote the numbers of vertices and edges, respectively. It is known that …