### Mining Important Sub-Graphs Using Skyline Approach over Vertex Connectivity Constraint

#### Abstract

#### Keywords

#### Full Text:

PDF#### References

A N.Papadopoulos, A. Lyritsis, and Y Manalopoulos, “SkyGraph: an algorithm for important subgraph discovery in relational graphs”, DMKD (2008), Springer, 23 Jun 2008, pp. 57-76.

Cook DJ, Holder L B (eds) (2007) Mining graph data. Wiley, London.

Hartuv E, Shamir R (2000), A Clustering algorithm based on Graph Connectivity. Inform Process Lett 76: 175-181.

Wu Z, Leahy R (1993) An optimal graphs theoretic approach to data clustering: theory and its application to image segmentation, IEEE Trans Pattern Anal Machine Intell 15(11): 1101-1113.

Hu H, Yan X, Huang Y, Han J, Zhou XJ (2005) Mining coherent dense subgraphs acrossmassive biological networks for functional discovery. Bioinformatics 21(1):i213–i221

Yan X, Mehan MR, Huang Y, Waterman MS, Yu PS, Zhou XJ (2007) A graph-based approach to systematically reconstruct human transcriptional regulatory modules. Bioinformatics 23(13):i577–i586

Bron,C. and Kerbosch,J. (1973) Finding All Cliques of an Undirected Graph. Communications of the ACM, 16: 575-577.

Chiba,N. and Nishizeki,T. (1985) Arboricity and Subgraph Listing Algorithms. SIAM J. Comput., 14:210-223.

T. Chakraborty, J. Chuzhoy and S. Khanna. Network Design for Vertex Connectivity. Proc. of ACM STOC, 2008.

Graph Theory. Addison-Wesley Publishing Company, Reading, Mass.Harley, E., Bonner, A.J., and Goodman, N. (2001) Uniform Integration of Genome Mapping Data Using Intersection Graphs. Bioinformatics 17: 487-494.

Johnston, H.C. (1976) Cliques of a Graph --- Variations on the Bron-Kerbosch Algorithm. International Journal of Computer and Information Sciences 5: 209-238.

Loukakis, E. (1983) A New Backtracking Algorithm for Generating the Family of Maximal Independent Sets of a Graph. Comp. and Maths. With Appls., 9: 583-589.

A. Hanneman and M. Riddle, “Introduction to social network methods,”online at http://www.faculty.ucr.edu/ hanneman/nettext/, 2005.

Moon, J.W. and Moser,L. (1965) On cliques in graphs. Israel J. Math 3: 23-28.

Pardalos, P.M. and Xue,J. (1994) The maximum clique problem. Journal of Global Optimization 4:301-328.

Pardalos, P.M., Bomze,I.M., Budinich,M. and Pelillo,M. (1999) The Maximum Clique Problem. in Handbook of Combinatorial Optimization, Supplement, Vol. A (Eds: Du,D.and Pardalos,P.M.), Kluwer Academic Publishers: 1-74.

Zhu F, Yan X, Han J, Yu PS (2007) gPrune: a constraint pushing framework for graph pattern mining. In: Proceedings of PAKDD conference, pp 388–400

YanX, Zhou XJ,Han J (2005) Mining closed relational graphs with connectivity constraints. In: Proceedings of ACM KDD conference, pp 324–333

T. Chakraborty, J. Chuzhoy and S. Khanna. Network Design for Vertex Connectivity. Proc. Of ACM STOC, 2008.

J. Chuzhoy and S. Khanna. Algorithms for Single-Source vertex-Connectivity. Proc. Of IEEE FOCS, October 2008.

S. Even, “An algorithm for determining whether the connectivity of a graph is at least k,” SIAM Journal of Computing 4 (1975), 393-396.

S. Even, Graph Algorithms, Computer Science, 1979.

S. Even and R. E. Tarjan, “Network flow and testing graph connectivity,” SIAM Journal of Computing 4 (1975), pp. 507-518.

A‐H. Esfahanian and S. L. Hakimi, “On computing the connectivities of graphs and digraphs,” NETWORKS, Vol. 14, pp. 355-366, 1984.

D. J. Kleitman, “Methods for investigating connectivity of large graphs,” IEEE Trans. Circuit Theory 16 (1969), pp. 232-233.

Y. Mansour and B. Schieber, “Finding the edge connectivity of directed graphs,” Journal of Algorithms 10 (1989), pp. 76-85.

D. W. Matula, “Determining edge connectivity in O(mn),” Proceedings of 28th Symp. on Foundations of Computer Science, (1987), pp. 249-251.

Z. Galil, “Finding the vertex connectivity of graphs,” SIAM Journal of Computing, 9 (1980), pp. 197199.

Z. Galil and G. F. Italiano, “Reducing edge connectivity to vertex connectivity,” ACM SIGACT News 22 (1991), pp. 57-61.

M. R. Henzinger, S. Rao and H. N. Gabow, “Computing vertex Connectivity : new bounds from old techniques,” Proc. 37th IEEE F. O. C.S. (1996), pp. 462-471.

C. P. Schnorr, “Bottlenecks and edge connectivity in unsymmetrical networks,” SIAM Journal of Computing 8 (1979), 265-274.

### Refbacks

- There are currently no refbacks.

This work is licensed under a Creative Commons Attribution 3.0 License.