DocumentCode
285671
Title
On graph bipartization
Author
Abdullah, Ahsan
Author_Institution
Dept. of Comput. Sci., Univ. of Southern California, Los Angeles, CA, USA
Volume
4
fYear
1992
fDate
3-6 May 1992
Firstpage
1847
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/ISCAS.1992.230393
Filename
230393
Link To Document