Search or add a thesis

Advanced Search (Beta)
Home > Combinatorial Generation Algorithms for Subgraphs

Combinatorial Generation Algorithms for Subgraphs

Thesis Info

Access Option

External Link

Author

Zareen Alamgir

Program

PhD

Institute

National University of Computer and Emerging Sciences

City

Karachi

Province

Sindh

Country

Pakistan

Thesis Completing Year

2013

Thesis Completion Status

Completed

Subject

Computer Science

Language

English

Link

http://prr.hec.gov.pk/jspui/bitstream/123456789/2308/1/2529S.pdf

Added

2021-02-17 19:49:13

Modified

2024-03-24 20:25:49

ARI ID

1676727716512

Asian Research Index Whatsapp Chanel
Asian Research Index Whatsapp Chanel

Join our Whatsapp Channel to get regular updates.

Similar


The field of computer science has greatly benefitted from the advances in combina- torial algorithms in the last few decades. This is because the advent of high speed computers has made it possible to generate lists of combinatorial objects in a practi- cal amount of time. In areas such as genome science and data mining the problems are often vaguely defined, and researchers have to look for meaningful information in huge datasets. In this thesis, efficient generation algorithms for subgraphs such as bicliques and paths in cliques are developed. Cliques and bicliques are used to model various real-world problems encountered in bio-informatics, data mining and networks. We consider two variations of bicliques: pseudo-bicliques and c-isolated bicliques. Pseudo- bicliques relax the rigid connectivity requirement of bicliques to cater for missing and noisy data. On the other hand, the c-isolated bicliques enforce a restriction on the external connectivity of the vertices in a biclique to model cohesive communities. This thesis presents an algorithm based on reverse search to list all pseudo-bicliques in a graph G. The algorithm takes linear time on average to generate each pseudo- biclique. On the other hand, our generation algorithm for c-isolated bicliques exploit underlying properties of an isolated biclique to trim the input graph. Furthermore, the algorithm deploys the vertex cover enumeration algorithm based on fixed point tractability (FTP) and lists all isolated bicliques in linear time, in the case where c is constant. The performance of the proposed algorithms is evaluated on random graphs and real-world problems. The results are quite promising and confirm our theoretical findings. In this research work, we also explore another combinatorial object called a clique. A constant amortized time algorithm is proposed to generate all spanning paths and all paths in a clique in minimal change order (an ordering in which successive elements differ in a small way)
Loading...
Loading...

Similar Books

Loading...

Similar Chapters

Loading...

Similar News

Loading...

Similar Articles

Loading...

Similar Article Headings

Loading...

استفہام بمعنی اقرار

استفہام بمعنی اقرار

بعض اوقات استفہام اقرار کے معنی میں استعمال ہوا ہے ۔ مقصد غور و تدبر کے بعد مخاطب کو اقرار واعتراف پر آمادہ کرنا ہے۔ قرآنی ادب میں اسلوب کے بڑے عمدہ طریقے سےاستعمال کیا گیا ہے ۔ جیسے :

"أَفَتُؤْمِنُونَ بِبَعْضِ الْكِتَابِ وَتَكْفُرُونَ بِبَعْضٍ فَمَا جَزَاءُ مَنْ يَفْعَلُ ذَلِكَ مِنْكُمْ إِلَّا خِزْيٌ فِي الْحَيَاةِ الدُّنْيَا”[[1]]

"کیاوہ بعض احکام پر ایمان رکھتے ہو اور بعض کے ساتھ کفر کرتے ہو (١) تم میں سے جو بھی ایسا کرے، اس کی سزا اس کے سوا کیا ہو کہ دنیا میں رسوائی) اس آیت میں اللہ تعالیٰ بنی اسرائیل سے ان کا یہ جرم باور کرانا چاہتاہے کہ تمہاری ازل سے یہ کوشش رہی ہے کہ تم کتاب کے اس حصے پر ایمان لاتے ہو جو تمہاری خواہشات کےمطابق ہو اور جو تمہاری ہوائےنفس کی تکمیل میں رکاوٹ بنے اس کا انکار کر دیتے ہو کیا تمہارے یہ رویہ نہیں رہا ہے" ۔

"أَلَمْ يَجْعَلْ كَيْدَهُمْ فِي تَضْلِيلٍ ، وَأَرْسَلَ عَلَيْهِمْ طَيْرًا أَبَابِيلَ"[[2]]

"کیا اس نے ان لوگوں کی ساری چالیں بیکار نہیں کر دی تھیں؟ او ران پرغول کے غول پرندے چھوڑ دیے تھے"۔

یہاں سوال کرنا مقصود نہیں بلکہ مخاطب کو یہ باور کرانا مقصود ہے کہ ایسا ہو چکاہے ۔

" قَالَ أَتَعْبُدُونَ مَا تَنْحِتُونَ (۹۵) وَاللَّهُ خَلَقَكُمْ وَمَا تَعْمَلُونَ"۔[[3]]

"تو آپ نے فرمایا تم انہیں پوجتے ہو جنہیں (خود) تم تراشتے ہو حالانکہ تمہیں اور تمہاری بنائی ہوئی چیزوں کو اللہ ہی نے پیدا کیا ہے "۔

قاضی ثناء اللہ پانی...

اندلس میں مسلمانوں کے ادوار حکومت کا تحقیقی و تنقیدی جائزہ

The golden Islamic history cannot be completed without the mention of Spain which was a bright star. It became one of the great Muslim civilizations; reaching its summit with the Umayyad caliphate of the tenth century. The heartland of Muslim rule was Southern Spain or Andulus. Different eras of Muslim rule in Andulus have been described in this research with an aim to highlight their apex and glory they achieved and then a focus on the reasons of their downfall as well. A brief introduction of the rulers in all eras with their major achievements and immersion in evil habits that led to their downfall has been the prime focus of this research. It gives us various glimpses from the course of history to reflect upon Muslim rule in Spain from a new perspective.

Development of Targeted Nano Drug Delivery System With Hybrid Materials for Cancer Therapy

Targeted treatment of cancer with new dexterous strategies using biocompatible materials is the hallmark of recent cancer research. In this study three innovative designs of targeted delivery systems with hybrid materials have been developed. Two nanosilica based passive systems are developed using stimuli specific to the tumour micro environment for the delivery of anticancer drugs. In zinc oxide based, active targeted system, the technique of receptor mediation through cancer cell membrane for its internalization has been adopted. The first system is hybrid material with nanosilica based bio-responsive drug delivery system. This system has been developed through a facile surface modification of the silica nanoparticles with biocompatible material. It showed higher entrapment efficiency for anticancer drug doxorubicin with sustained drug release behaviour in vitro. Unique feature of surface charge swapping in response to the lower pH of the tumour microenvironment significantly increased the cellular internalization of the nanocarriers into the tumour tissue as compared to other vital organs. The increased uptake and controlled release of anticancer drug co-jointly contributed to suppress the tumour growth in squamous cell carcinoma (SCC7) bearing nude mice. The second nanosilica based passive targeted system focused to target the hypoxic conditions of tumour. Surface modification of the nanoparticles with biocompatible moieties made the system nontoxic for biomedical applications These PEGylated hypoxia responsive nanocarriers contained higher amount of the anticancer drug and showed sustained release of the drug in hypoxic environment with no premature release in physiological or normoxic conditions. The third system is active targeted carrier possessing core material of zinc oxide functionalized with hyaluronic acid as targeting moiety. The system showed significantly improved cellular uptake, due to receptor mediated endocytosis in T-cells, with controlled release of anticancer drug. Doxorubicin loaded nanocarriers along with methyl aminolevulinate (m-ALA) showed increased cancer cell destruction in RD cells. The biocompatibility, drug loading and its release characteristics, cell uptake, intra cellular drug release, and antitumor efficacy have been evaluated for the above systems. The obtained results exhibited the success of the carriers for their biological response. These newly designed targeted delivery systems fabricated with hybrid materials possess strong potential to open new horizons in of controlled and site specific delivery of anticancer drugs with increased bioavailability and improved therapeutic efficacy