Computer Science – Theory and Applications
14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1–5, 2019, Proceedings
Page
%P
21 Result(s)
within
René van Bevern
Discrete Mathematics in Computer Science
-
Book and Conference Proceedings
-
Chapter and Conference Paper
Fixed-Parameter Algorithms for Maximum-Profit Facility Location Under Matroid Constraints
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
On \((1+\varepsilon )\) -approximate Data Reduction for the Rural Postman Problem
Given a graph
-
Chapter and Conference Paper
Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks
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
Parameterizing Edge Modification Problems Above Lower Bounds
For a fixed graph F, we study the parameterized complexity of a variant of the \(F\text {-}{\textsc {free\ Editing}}\) ...
-
Chapter and Conference Paper
Twins in Subdivision Drawings of Hypergraphs
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
Completing Partial Schedules for Open Shop with Unit Processing Times and Routing
Open Shop is a classical scheduling problem: given a set \(\mathcal J\) of jobs and a set ...
-
Chapter and Conference Paper
Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
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
Network-Based Dissolution
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
Star Partitions of Perfect Graphs
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
Myhill-Nerode Methods for Hypergraphs
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
A Parameterized Complexity Analysis of Combinatorial Feature Selection Problems
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
Parameterized Complexity of DAG Partitioning
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
On the Parameterized Complexity of Computing Graph Bisections
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
Interval Scheduling and Colorful Independent Sets
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
Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs
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
Towards Optimal and Expressive Kernelization for d-Hitting Set
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
From Few Components to an Eulerian Graph by Adding Arcs
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
A New View on Rural Postman Based on Eulerian Extension and Matching
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
Measuring Indifference: Unit Interval Vertex Deletion
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...
