Thesis Topic Details
Topic ID: |
3400 | |
Title: |
Lower bounds for extremal vertex sets in graphs | |
Supervisor: |
Serge Gaspers | |
Research Area: |
Algorithms, Theory, Discrete Mathematics | |
| Associated Staff | ||
|---|---|---|
Assessor: |
Toby Walsh | |
| Topic Details | ||
Status: |
Active | |
Type: |
Research | |
Programs: |
CS CE BIOM BINF SE | |
Group Suitable: |
No | |
Industrial: |
No | |
Pre-requisites: |
-- | |
Description: |
A dominating set in a graph is a subset of vertices such that every vertex outside the set has a neighbor in the set. A dominating set is minimal (by inclusion) if it does not contain another dominating set as a subset. It is known that the number of minimal dominating sets in a graph on n vertices is at most 1.7697^n. On the other hand, there exist infinitely many graphs with 15^(n/6) > 1.5704^n minimal dominating sets. The family of graphs providing this lower bound is a disjoint union of n/6 octahedrons, the octahedron being a small graph on 6 vertices with 15 minimal dominating sets. The aim of this thesis is to find lower bounds for the number of various extremal vertex sets in graphs, such as minimal dominating sets, minimal separators, minimal feedback vertex sets, etc. One plausible approach is to systematically enumerate and analyze all small graphs with the help of a computer, as building blocks for the graphs providing the lower bounds. In some cases, e.g., minimal dominating sets, it is trivial to assemble these building blocks. In other cases, e.g., minimal separators, more ingenious methods are needed for their assembly. Bounds of this kind are motivated by the analysis of algorithmic running times. For instance, the bound on minimal dominating sets arises in the analysis of algorithms for computing the domatic number, which has applications in facility-location problems in networks. The thesis requires very good programming skills, with a focus on code profiling and optimization, and working with succinct representations of graphs, in order to be able to analyze a maximum number of building blocks. |
|
Comments: |
-- | |
| Past Student Reports | ||
| No Reports Available. Contact the supervisor for more information.
Check out all available reports in the CSE Thesis Report Library. NOTE: only current CSE students can login to view and select reports to download. |
||