Thesis Topic Details

Topic ID:
3401
Title:
Measure and Conquer for Efficient Edge Domination
Supervisor:
Serge Gaspers
Research Area:
Algorithms, Theory, Discrete Mathematics
Associated Staff
Assessor:
Aleksandar Ignjatovic
Topic Details
Status:
Active
Type:
Research
Programs:
CS CE BIOM BINF SE
Group Suitable:
No
Industrial:
No
Pre-requisites:
--
Description:
In a graph, an edge is said to dominate itself and all edges incident to it. An efficient edge dominating set in a graph is a subset of edges such that every edge is dominated by exactly one edge from this set. The Efficient Edge Domination problem (EED) is, for an input graph G, to decide whether G has an efficient edge dominating set. EED is NP-complete and the fastest known algorithm has worst-case running time O(1.1939^n), where n is the number of vertices of G [http://arxiv.org/abs/1303.0035].

EED is also known as Dominating Induced Matching and has applications in encoding theory, network routing, and resource allocation.

The aim of this project is to design and analyze an algorithm for EED using the Measure and Conquer framework, and improving on the running time of the fastest known algorithm for this problem. The Measure and Conquer method assigns a potential function (measure) to an input instance and tracks the progress of an algorithm in a more refined way.
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.