Computer Science – Theory and Applications
14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1–5, 2019, Proceedings
Book and Conference Proceedings
14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1–5, 2019, Proceedings
Chapter and Conference Paper
We consider an uncapacitated discrete facility location problem where the task is to decide which facilities to open and which clients to serve for maximum profit so that the facilities form an independent set...
Chapter and Conference Paper
Given a graph
Chapter and Conference Paper
We study an NP-hard problem motivated by energy-efficiently maintaining the connectivity of a symmetric wireless sensor communication network. Given an edge-weighted
Chapter and Conference Paper
For a fixed graph F, we study the parameterized complexity of a variant of the \(F\text {-}{\textsc {free\ Editing}}\) ...
Chapter and Conference Paper
Visualizing hypergraphs, systems of subsets of some universe, has continuously attracted research interest in the last decades. We study a natural kind of hypergraph visualization called subdivision drawings. Din...
Chapter and Conference Paper
Open Shop is a classical scheduling problem: given a set \(\mathcal J\) of jobs and a set ...
Chapter and Conference Paper
Negatively answering a question posed by Mnich and Wiese (Math. Program. 154(1–2):533–562), we show that $$\hbox {P2}|\hbox {prec}, p_...
Chapter and Conference Paper
We introduce a graph-theoretic dissolution model that applies to a number of redistribution scenarios such as gerrymandering in political districting or work balancing in an online situation. The central aspec...
Chapter and Conference Paper
The partition of graphs into nice subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into stars, a problem known to be NP-complete ev...
Chapter and Conference Paper
We introduce a method of applying Myhill-Nerode methods from formal language theory to hypergraphs and show how this method can be used to obtain the following parameterized complexity results.
Chapter and Conference Paper
We examine the algorithmic tractability of NP-hard combinatorial feature selection problems in terms of parameterized complexity theory. In combinatorial feature selection, one seeks to discard dimensions from...
Chapter and Conference Paper
The goal of tracking the origin of short, distinctive phrases (memes) that propagate through the web in reaction to current events has been formalized as DAG Partitioning: given a directed acyclic graph, delete e...
Chapter and Conference Paper
The Bisection problem asks for a partition of the vertices of a graph into two equally sized sets, while minimizing the cut size. This is the number of edges connecting the two vertex sets. Bisection has been tho...
Chapter and Conference Paper
The NP-hard Independent Set problem is to determine for a given graph G and an integer k whether G contains a set of k pairwise non-adjacent vertices. The problem has numerous applications in scheduling, includin...
Chapter and Conference Paper
We present a linear-time kernelization algorithm that transforms a given planar graph G with domination number γ(G) into a planar graph G′ of size O(γ(G)) with γ(G) = γ(G′). In addition, a minimum dominating set ...
Chapter and Conference Paper
A sunflower in a hypergraph is a set of hyperedges pairwise intersecting in exactly the same vertex set. Sunflowers are a useful tool in polynomial-time data reduction for problems formalizable as d-Hitting Set, ...
Chapter and Conference Paper
Eulerian Extension (EE) is the problem to make an arc-weighted directed multigraph Eulerian by adding arcs of minimum total cost. EE is NP-hard and has been shown fixed-parameter tractable with res...
Chapter and Conference Paper
We provide a new characterization of the NP-hard arc routing problem Rural Postman in terms of a constrained variant of minimum-weight perfect matching on bipartite graphs. To this end, we employ a parameterized ...
Chapter and Conference Paper
Making a graph unit interval by a minimum number of vertex deletions is NP-hard. The problem is motivated by applications in seriation and measuring indifference between data items. We present a fixed-paramete...