Aarhus University Seal / Aarhus Universitets segl

Edvin Berglin

Geometric covers, graph orientations, counter games

Research output: Book/anthology/dissertation/reportPh.D. thesisResearch

Standard

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

Aarhus : Aarhus Universitet, 2017. 83 p.

Research output: Book/anthology/dissertation/reportPh.D. thesisResearch

Harvard

APA

CBE

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

MLA

Vancouver

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

Author

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

Bibtex

@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",

}

RIS

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 -