Research output: Book/anthology/dissertation/report › Ph.D. thesis › Research

**Geometric covers, graph orientations, counter games.** / Berglin, Edvin.

Research output: Book/anthology/dissertation/report › Ph.D. thesis › Research

Berglin, E 2017, *Geometric covers, graph orientations, counter games*. Aarhus Universitet, Aarhus.

Berglin, E. (2017). *Geometric covers, graph orientations, counter games*. Aarhus: Aarhus Universitet.

Berglin E 2017. Geometric covers, graph orientations, counter games. Aarhus: Aarhus Universitet. 83 p.

Berglin, Edvin *Geometric covers, graph orientations, counter games* Aarhus: Aarhus Universitet. 2017.

Berglin E. Geometric covers, graph orientations, counter games. Aarhus: Aarhus Universitet, 2017. 83 p.

Berglin, Edvin. / **Geometric covers, graph orientations, counter games**. Aarhus : Aarhus Universitet, 2017. 83 p.

@phdthesis{ecdfaea81deb4401bfefcc5f0577aa0b,

title = "Geometric covers, graph orientations, counter games",

abstract = "Geometric Cover is a large family of NP-complete special cases of the broader Set Cover problem.Unlike the general problem, Geometric Cover involves objects that exist in a geometric setting,consequently implying that they are all restricted to obeying some inherent structure. Thearchetypal example is Line Cover, also known as Point-Line Cover, where a set of points ina geometric space are to be covered by placing a restricted number of lines. We present newFPT algorithms for the sub-family Curve Cover (which includes Line Cover), as well as forHyperplane Cover restricted to R 3 (i.e. Plane Cover), with improved time complexity comparedto the previous best results. Our improvements are derived from a more careful treatment ofthe geometric properties of the covering objects than before, and invoking incidence boundsfrom pure geometry.An orientation of an un-directed graph is a directed version of it, i.e. where every un-directededge in the original graph has been replaced by a directed edge, incident on the same two vertices,in either direction. Graph orientations with low out-degree are desirable as the foundation ofdata structures with many applications. If the un-directed graph is dynamic (can be alteredby some outside actor), some orientations may need to be reversed in order to maintain thelow out-degree. We present a new algorithm that is simpler than earlier work, yet matches oroutperforms the efficiency of these results with very few exceptions.Counter games are a type of abstract game played over a set of counters holding values,and these values may be moved between counters according to some set of rules. Typicallythey are played between two players: the adversary who tries to concentrate the greatest valuepossible in a single counter, and the benevolent player who tries to prevent the adversary fromdoing so. These counter games are sometimes used as a behind-the-scenes tool for proving theefficiency of an algorithm, i.e. proving that the adversary is unable concentrate more than somespecific value in a counter, also proves that the algorithm cannot perform worse than this value.We develop a new counter game with only one player (the adversary), and use it to prove theefficiency of the graph orientation algorithm.",

author = "Edvin Berglin",

year = "2017",

month = "12",

day = "11",

language = "English",

publisher = "Aarhus Universitet",

}

TY - BOOK

T1 - Geometric covers, graph orientations, counter games

AU - Berglin, Edvin

PY - 2017/12/11

Y1 - 2017/12/11

N2 - Geometric Cover is a large family of NP-complete special cases of the broader Set Cover problem.Unlike the general problem, Geometric Cover involves objects that exist in a geometric setting,consequently implying that they are all restricted to obeying some inherent structure. Thearchetypal example is Line Cover, also known as Point-Line Cover, where a set of points ina geometric space are to be covered by placing a restricted number of lines. We present newFPT algorithms for the sub-family Curve Cover (which includes Line Cover), as well as forHyperplane Cover restricted to R 3 (i.e. Plane Cover), with improved time complexity comparedto the previous best results. Our improvements are derived from a more careful treatment ofthe geometric properties of the covering objects than before, and invoking incidence boundsfrom pure geometry.An orientation of an un-directed graph is a directed version of it, i.e. where every un-directededge in the original graph has been replaced by a directed edge, incident on the same two vertices,in either direction. Graph orientations with low out-degree are desirable as the foundation ofdata structures with many applications. If the un-directed graph is dynamic (can be alteredby some outside actor), some orientations may need to be reversed in order to maintain thelow out-degree. We present a new algorithm that is simpler than earlier work, yet matches oroutperforms the efficiency of these results with very few exceptions.Counter games are a type of abstract game played over a set of counters holding values,and these values may be moved between counters according to some set of rules. Typicallythey are played between two players: the adversary who tries to concentrate the greatest valuepossible in a single counter, and the benevolent player who tries to prevent the adversary fromdoing so. These counter games are sometimes used as a behind-the-scenes tool for proving theefficiency of an algorithm, i.e. proving that the adversary is unable concentrate more than somespecific value in a counter, also proves that the algorithm cannot perform worse than this value.We develop a new counter game with only one player (the adversary), and use it to prove theefficiency of the graph orientation algorithm.

AB - Geometric Cover is a large family of NP-complete special cases of the broader Set Cover problem.Unlike the general problem, Geometric Cover involves objects that exist in a geometric setting,consequently implying that they are all restricted to obeying some inherent structure. Thearchetypal example is Line Cover, also known as Point-Line Cover, where a set of points ina geometric space are to be covered by placing a restricted number of lines. We present newFPT algorithms for the sub-family Curve Cover (which includes Line Cover), as well as forHyperplane Cover restricted to R 3 (i.e. Plane Cover), with improved time complexity comparedto the previous best results. Our improvements are derived from a more careful treatment ofthe geometric properties of the covering objects than before, and invoking incidence boundsfrom pure geometry.An orientation of an un-directed graph is a directed version of it, i.e. where every un-directededge in the original graph has been replaced by a directed edge, incident on the same two vertices,in either direction. Graph orientations with low out-degree are desirable as the foundation ofdata structures with many applications. If the un-directed graph is dynamic (can be alteredby some outside actor), some orientations may need to be reversed in order to maintain thelow out-degree. We present a new algorithm that is simpler than earlier work, yet matches oroutperforms the efficiency of these results with very few exceptions.Counter games are a type of abstract game played over a set of counters holding values,and these values may be moved between counters according to some set of rules. Typicallythey are played between two players: the adversary who tries to concentrate the greatest valuepossible in a single counter, and the benevolent player who tries to prevent the adversary fromdoing so. These counter games are sometimes used as a behind-the-scenes tool for proving theefficiency of an algorithm, i.e. proving that the adversary is unable concentrate more than somespecific value in a counter, also proves that the algorithm cannot perform worse than this value.We develop a new counter game with only one player (the adversary), and use it to prove theefficiency of the graph orientation algorithm.

M3 - Ph.D. thesis

BT - Geometric covers, graph orientations, counter games

PB - Aarhus Universitet

CY - Aarhus

ER -