| You are in:Home/Publications/ M. I. Moussa and E. M. Badr (2012): A Computational Study for the Graph-Theoretic Version of the Union-Closed Sets Conjecture, International Journal of Computer Applications, Volume 50 – No.12, July 2012. | |
Prof. Alsayed alsayed mitwali badr :: Publications: |
|
| Title: | M. I. Moussa and E. M. Badr (2012): A Computational Study for the Graph-Theoretic Version of the Union-Closed Sets Conjecture, International Journal of Computer Applications, Volume 50 – No.12, July 2012. |
| Authors: | M. I. Moussa and E. M. Badr |
| Year: | 2012 |
| Keywords: | Not Available |
| Journal: | Not Available |
| Volume: | Not Available |
| Issue: | Not Available |
| Pages: | Not Available |
| Publisher: | Not Available |
| Local/International: | International |
| Paper Link: | |
| Full paper | Alsayed alsayed mitwali badr_pxc3880945.pdf |
| Supplementary materials | Not Available |
| Abstract: |
An induced subgraph S of a graph G is called a derived subgraph of G if S contains no isolated vertices. An edge e of G is said to be residual if e occurs in more than half of the derived subgraphs of G. We prove some theorems which calculate the number of derived subgraphs for some special graphs. We also present a new algorithm SDSA that calculates the number of derived subgraphs for a given graph G and determines the residual and non-residual edges. Finally, we introduce a computational study which supports our results. |
