The Library
Structural solutions to maximum independent set and related problems
Tools
Dabrowski, Konrad K. (2012) Structural solutions to maximum independent set and related problems. PhD thesis, University of Warwick.

Text
WRAP_THESIS_Dabrowski_2012.pdf  Submitted Version Download (1367Kb)  Preview 
Official URL: http://webcat.warwick.ac.uk/record=b2613049~S1
Abstract
In this thesis, we study some fundamental problems in algorithmic graph theory. Most
natural problems in this area are hard from a computational point of view. However,
many applications demand that we do solve such problems, even if they are intractable.
There are a number of methods in which we can try to do this:
1) We may use an approximation algorithm if we do not necessarily require the best
possible solution to a problem.
2) Heuristics can be applied and work well enough to be useful for many applications.
3) We can construct randomised algorithms for which the probability of failure is very
small.
4) We may parameterize the problem in some way which limits its complexity.
In other cases, we may also have some information about the structure of the
instances of the problem we are trying to solve. If we are lucky, we may and that we
can exploit this extra structure to find efficient ways to solve our problem. The question
which arises is  How far must we restrict the structure of our graph to be able to solve
our problem efficiently?
In this thesis we study a number of problems, such as Maximum Indepen
dent Set, Maximum Induced Matching, StableII, Efficient Edge Domina
tion, Vertex Colouring and Dynamic EdgeChoosability. We try to solve problems
on various hereditary classes of graphs and analyse the complexity of the resulting
problem, both from a classical and parameterized point of view.
Item Type:  Thesis (PhD)  

Subjects:  Q Science > QA Mathematics  
Library of Congress Subject Headings (LCSH):  Graph theory, Algorithms, Set theory, Problem solving  
Official Date:  October 2012  
Dates: 


Institution:  University of Warwick  
Theses Department:  Mathematics Institute  
Thesis Type:  PhD  
Publication Status:  Unpublished  
Supervisor(s)/Advisor:  Lozin, Vadim V.  
Sponsors:  University of Warwick. Mathematics Institute; University of Warwick. Centre for Discrete Mathematics and Its Applications; Engineering and Physical Sciences Research Council (EPSRC) (EP/D063191/1)  
Extent:  viii, 144 leaves.  
Language:  eng 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 
Downloads
Downloads per month over past year