Skip to content

theBrownBug/COM3610

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

31 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

COM3610 Dissertation (Deletion Into Small Components Problem)

Abstract

This research project aims to implement a Fixed Parameterized Complexity based algorithm for the Deletion into small Components Problem with and without heuristical improvements. The problem states that given a graph G, an integer k and an integer c, the problem checks whether there exists a deletion set D of size at most k such that every connected component in G\D has size at most c. This problem is NP complete. It has applications in testing computer network vulnerability and AI planning.

PseudoCode Of Algorithms Implemented

Simple Algorithm PseudoCode (without Heuristical Improvement)

Simple Algorithm

Simple Kernelised Algorithm

Kernelised Algorithm

Algorithm with Symmetry Breaking

Kernelised Algorithm

About

Dissertation

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages