On graph bipartization
A. Abdullah · 2003
The author discusses an undirected, connected graph G(V,E) without multiple edges and self loops. The minimum node (edge) deletion bipartite subgraph problem for G(V,E) is considered. Constant time computable upper and lower bounds are presented on the number of nodes (edges) deleted. The bounds are useful when very little is known about G(V,E). Heuristic solutions for each of these problems are introduced. The time complexity of both heuristics is O( mod V mod /sup 2/).>