Senger, Fabian Johannes (2018). On Equidomination in Graphs. PhD thesis, Universität zu Köln.

This is the latest version of this item.

[img]
Preview
PDF
Senger_On_Equidomination_in_Graphs.pdf - Published Version

Download (960kB)

Abstract

A graph G=(V,E) is called equidominating if there exists a value t in IN and a weight function w : V -> IN such that the total weight of a subset D of V is equal to t if and only if D is a minimal dominating set. Further, w is called an equidominating function, t a target value and the pair (w,t) an equidominating structure. To decide whether a given graph is equidominating is referred to as the EQUIDOMINATION problem. First, we examine several results on standard graph classes and operations with respect to equidomination. Furthermore, we characterize hereditarily equidominating graphs. These are the graphs whose every induced subgraph is equidominating. For those graphs, we give a finite forbidden induced subgraph characterization and a structural decomposition. Using this decomposition, we state a polynomial time algorithm that recognizes hereditarily equidominating graphs. We introduce two parameterized versions of the EQUIDOMINATION problem: the k-EQUIDOMINATION problem and the TARGET-t EQUIDOMINATION problem. For k in IN, a graph is called k-equidominating if we can identify the minimal dominating sets using only weights from 1 to k. In other words, if an equidominating function with co-domain {1,...,k} exists. For t in IN, a graph is said to be target-t equidominating if there is an equidominating structure with target value t. For both parameterized problems we prove fixed-parameter tractability. The first step for this is to achieve the so-called pseudo class partition, which coarsens the twin partition. It is founded on the requirement that vertices from different blocks of the partition cannot have equal weights in any equidominating structure. Based on the pseudo class partition, we state an XP algorithm for the parameterized versions of the EQUIDOMINATION problem. The second step is the examination of three reduction rules - each of them concerning a specific type of block of the pseudo class partition - which we use to construct problem kernels. The sizes of the kernels are bounded by a function depending only on the respective parameter. By applying the XP algorithm to the kernels, we achieve FPT algorithms. The concept of equidomination was introduced nearly 40 years ago, but hardly any investigations exist. With this thesis, we want to fill that gap. We may lay the foundation for further research on equidomination.

Item Type: Thesis (PhD thesis)
Creators:
CreatorsEmailORCID
Senger, Fabian Johannessenger.fabian@gmx.deUNSPECIFIED
URN: urn:nbn:de:hbz:38-80894
Series Name: Informatik
Publisher: München: Hut
ISBN: 978-3-8439-3489-3
Subjects: Data processing Computer science
Mathematics
Uncontrolled Keywords:
KeywordsLanguage
Graph Theory; Parameterized Complexity; EquidominationUNSPECIFIED
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Institute of Computer Science
Language: English
Date: 2018
Date of oral exam: 19 December 2017
Referee:
NameAcademic Title
Schrader, RainerProf. Dr.
Schaudt, OliverProf. Dr.
Related URLs:
Refereed: Yes
URI: http://kups.ub.uni-koeln.de/id/eprint/8090

Downloads

Downloads per month over past year

Export

Available Versions of this Item

  • On Equidomination in Graphs. (deposited 12 Mar 2018 14:21) [Currently Displayed]

Actions (login required)

View Item View Item