Improved and More Realistic Algorithms for Maximal Graph Connectivity


Norbert Zeh

Author Addresses: 

Faculty of Computer Science
Dalhousie University
6050 University Ave.
PO Box 15000
Halifax, Nova Scotia, Canada
B3H 4R2


We study the maximal connectivity problem (MCP), which is defined as follows: Given a set V of n vertices and a set E of m pairwise disjoint edge pairs, we define a family G(V, E) as the set of multigraphs that have vertex set V and contain exactly one edge from every pair in E. We want to find a multigraph in G(V, E) that has the minimal number of connected components. We present an O(nm)-time algorithm for this problem. Our result is obtained by avoiding the explicit construction of the auxiliary graph of [21] and querying only the relevant parts of the graph when needed. Our second result studies graph families G(V, E) that are derived from a surface simplification problem described in [8]. This problem was the initial motivation for studying MCP. The edge pairs in these families are non-disjoint; but their structure is restricted enough to allow an efficient solution of MCP on these families. In particular, the NP-hardness proof for MCP on general families G(V, E) such that the edge pairs in E are non-disjoint does not apply.

Tech Report Number: 
Report Date: 
March 17, 2004
PDF icon CS-2004-04.pdf483.82 KB