Welcome to our book review site go-pdf.online!
You may have to Search all our reviewed books and magazines, click the sign up button below to create a free account.
Event structures with higher-order dynamics
Event Structure were introduced in 1979 [18] as a formal model to connect the theory of Petri nets and domain theory. Originally they consisted of atomic non-repeatable events, a binary causal dependency relation, and a binary conflict relation between those events. For a long time various extensions of the original formalism were used to define semantics for other structures such as classes of Petri nets and process calculi.In this thesis the Event Structures (ESs) are considered solely as a declarative modelling tool than as a formalism to define semantics for other structures. In order to model highly dynamic real-world processes (i.e. processes in which occurrences of events may change t...
On the feasibility of multi-leader replication in the early tiers
In traditional service architectures that follow the service statelessness principle, the state is primarily held in the data tier. Here, service operators utilize tailored storage solutions to guarantee the required availability; even though failures can occur at any time. This centralized approach to store and process an application’s state in the data tier implies that outages of the entire tier cannot be tolerated. An alternative approach, which is in focus of this thesis, is to decentralize the processing of state information and to use more stateful components in the early tiers. The possibility to tolerate a temporary outage of an entire tier implies that the application’s state c...
Be sparse! Be dense! Be robust!
In this thesis we study the computational complexity of five NP-hard graph problems. It is widely accepted that, in general, NP-hard problems cannot be solved efficiently, that is, in polynomial time, due to many unsuccessful attempts to prove the contrary. Hence, we aim to identify properties of the inputs other than their length, that make the problem tractable or intractable. We measure these properties via parameters, mappings that assign to each input a nonnegative integer. For a given parameter k, we then attempt to design fixed-parameter algorithms, algorithms that on input q have running time upper bounded by f(k(q)) * |q|^c , where f is a preferably slowly growing function, |q| is t...
Algorithmic aspects of resource allocation and multiwinner voting: theory and experiments
This thesis is concerned with investigating elements of computational social choice in the light of real-world applications. We contribute to a better understanding of the areas of fair allocation and multiwinner voting. For both areas, inspired by real-world scenarios, we propose several new notions and extensions of existing models. Then, we analyze the complexity of answering the computational questions raised by the introduced concepts. To this end, we look through the lens of parameterized complexity. We identify different parameters which describe natural features specific to the computational problems we investigate. Exploiting the parameters, we successfully develop efficient algorit...
Classic graph problems made temporal – a parameterized complexity analysis
This thesis investigates the parameterized computational complexity of six classic graph problems lifted to a temporal setting. More specifically, we consider problems defined on temporal graphs, that is, a graph where the edge set may change over a discrete time interval, while the vertex set remains unchanged. Temporal graphs are well-suited to model dynamic data and hence they are naturally motivated in contexts where dynamic changes or time-dependent interactions play an important role, such as, for example, communication networks, social networks, or physical proximity networks. The most important selection criteria for our problems was that they are well-motivated in the context of dyn...
Elements of dynamic and 2-SAT programming: paths, trees, and cuts
In dieser Arbeit entwickeln wir schnellere exakte Algorithmen (schneller bezüglich der Worst-Case-Laufzeit) für Spezialfälle von Graphproblemen. Diese Algorithmen beruhen größtenteils auf dynamischem Programmieren und auf 2-SAT-Programmierung. Dynamisches Programmieren beschreibt den Vorgang, ein Problem rekursiv in Unterprobleme zu zerteilen, sodass diese Unterprobleme gemeinsame Unterunterprobleme haben. Wenn diese Unterprobleme optimal gelöst wurden, dann kombiniert das dynamische Programm diese Lösungen zu einer optimalen Lösung des Ursprungsproblems. 2-SAT-Programmierung bezeichnet den Prozess, ein Problem durch eine Menge von 2-SAT-Formeln (aussagenlogische Formeln in konjunkti...
Fine-grained complexity analysis of some combinatorial data science problems
This thesis is concerned with analyzing the computational complexity of NP-hard problems related to data science. For most of the problems considered in this thesis, the computational complexity has not been intensively studied before. We focus on the complexity of computing exact problem solutions and conduct a detailed analysis identifying tractable special cases. To this end, we adopt a parameterized viewpoint in which we spot several parameters which describe properties of a specific problem instance that allow to solve the instance efficiently. We develop specialized algorithms whose running times are polynomial if the corresponding parameter value is constant. We also investigate in wh...
Parity games, separations, and the modal μ-calculus
The topics of this thesis are the modal μ-calculus and parity games. The modal μ-calculus is a common logic for model-checking in computer science. The model-checking problem of the modal μ-calculus is polynomial time equivalent to solving parity games, a 2-player game on labeled directed graphs. We present the first FPT algorithms (fixed-parameter tractable) for the model-checking problem of the modal μ-calculus on restricted classes of graphs, specifically on classes of bounded Kelly-width or bounded DAG-width. In this process we also prove a general decomposition theorem for the modal μ-calculus and define a useful notion of type for this logic. Then, assuming a class of parity games...
Dualities in graphs and digraphs
In this thesis we describe dualities in directed as well as undirected graphs based on tools such as width-parameters, obstructions and substructures. We mainly focus on directed graphs and their structure. In the context of a long open conjecture that bounds the monotonicity costs of a version of the directed cops and robber game, we introduce new width-measures based on directed separations that are closely related to DAG-width. We identify a tangle-like obstruction for which we prove a duality theorem. Johnson, Reed, Robertson, Seymour and Thomas introduced the width measure directed treewidth as a generalisation of treewidth for directed graphs. We introduce a new width measure, the cycl...
Matching minors in bipartite graphs
In this thesis we adapt fundamental parts of the Graph Minors series of Robertson and Seymour for the study of matching minors and investigate a connection to the study of directed graphs. We develope matching theoretic to established results of graph minor theory: We characterise the existence of a cross over a conformal cycle by means of a topological property. Furthermore, we develope a theory for perfect matching width, a width parameter for graphs with perfect matchings introduced by Norin. here we show that the disjoint alternating paths problem can be solved in polynomial time on graphs of bounded width. Moreover, we show that every bipartite graph with high perfect matching width mus...
