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, Stable-II, Efficient Edge Domina-
tion, Vertex Colouring and Dynamic Edge-Choosability. 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