Title :
On graph bipartization
Author_Institution :
Dept. of Comput. Sci., Univ. of Southern California, Los Angeles, CA, USA
Abstract :
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 (|V|2)
Keywords :
computational complexity; graph theory; connected graph; constant time computable bounds; edge deletion problem; graph bipartization; lower bounds; minimum node deletion problem; number of deletions; partition; time complexity; undirected graphs; upper bounds; without multiple edges; without self loops; Application software; Bipartite graph; Computer applications; Computer science; NP-complete problem; Printed circuits; Tiles; Upper bound;
Conference_Titel :
Circuits and Systems, 1992. ISCAS '92. Proceedings., 1992 IEEE International Symposium on
Conference_Location :
San Diego, CA
Print_ISBN :
0-7803-0593-0
DOI :
10.1109/ISCAS.1992.230393
