Maximum clique in a graph

Details Maximum clique in a graph Maximum clique in a graph

2011-07-26

2011-07-26

Chankong, Dohm (Department: 2452)

Electrical computers and digital processing systems: multicomput

Computer network managing

C370S254000, C370S255000

Reexamination Certificate

active

07987250

ABSTRACT:
A method and system for maximizing connectivity within members of a group, or for example a clique, in polynomial time. Vertices representing inter-connectivity of each member are placed on a graph in descending order. Least connected members are systematically removed from the graph until the connectivity count of a least connected vertex is equal to a quantity of vertices remaining in the graph. Following the removal of a vertex from the graph, an update of the inter-connectivity of each member on the graph is performed. Accordingly, when the connectivity count of a least connected vertex is equal to a quantity of vertices remaining in the graph a clique with maximum inter-connectivity has been achieved.

REFERENCES:
patent: 4821157 (1989-04-01), Birk et al.
patent: 5446908 (1995-08-01), Kevorkian
patent: 5515383 (1996-05-01), Katoozi
patent: 5655137 (1997-08-01), Kevorkian
patent: 5884018 (1999-03-01), Jardine et al.
patent: 6002851 (1999-12-01), Basavaiah et al.
patent: 6240463 (2001-05-01), Benmohamed et al.
patent: 6327387 (2001-12-01), Naoi et al.
patent: 6374297 (2002-04-01), Wolf et al.
patent: 6437804 (2002-08-01), Ibe et al.
patent: 6449743 (2002-09-01), Hosokawa
patent: 6594624 (2003-07-01), Curet
patent: 6795399 (2004-09-01), Benmohamed et al.
patent: 6990080 (2006-01-01), Bahl et al.
patent: 7512703 (2009-03-01), Ho et al.
patent: 2003/0026268 (2003-02-01), Navas
patent: 2004/0151121 (2004-08-01), Natarajan et al.
patent: 2004/0156321 (2004-08-01), Walker et al.
Ostergard, P.R.J, “A Fast Algorithm for the Maximum Clique Problem,” Discrete Applied Mathematics, vol. 120, pp. 197-207, 2002.
Pardalos et al, “An Exact Parallel Algorithm for the Maximum Clique Problem,” High performance algorithms and software in nonlinear optimization. Kluwer Academic Publishers, 1998.
V. Bouchitte et al, “Listing all potential maximal cliques of a graph,” Lecture Notes in Computer Science—Proceedings of teh 17th Annual Symposium on Theoretical Aspects of Computer Science, vol. 1770, pp. 503-515, 2000.
Coudert, Olivier, “Exact Coloring of Real-Life Graphs is Easy,” Annual ACM IEEE Design Automation Conference, pp. 121-126, 1997.
Jagota, Arun, “Optimization by reduction to maximum clique,” IEEE International Conference on Neural Networks, vol. 3, pp. 1526-1531, 1993.
Szymanski, et al, “Spanning tree algorithm for spare network capacity,” Canadian Conference on Electrical and Computer Engineering, vol. 1., pp. 447-452, 2001.
Bomze et al, “The Maximum Clique Problem,” Handbook of Combinatorial Optimization, pp. 1-74, Kluwer Academic Publishers, 1999.
J. Abello, M. G. C. Resende, and S. Sudarsky. Massive quasi-clique detection. Latin: Latin American Symposium on Theoretical Informatics, 2286:598-612, 2002.
Pardalos et al., “The maximum clique problem”, Journal of Global Optimization, pp. 301-328, 1994.

Affiliated with

Also associated with

Rating

Maximum clique in a graph does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Maximum clique in a graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum clique in a graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2652604