Computer Science – Theory and Applications
14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1–5, 2019, Proceedings
Page
%P
-
Article
Special Issue on Computer Science Symposium in Russia (2019)
-
Article
Inductive \(k\) -independent graphs and c-colorable subgraphs in scheduling: a review
Inductive \(k\) k ...
-
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
-
Article
Parameterizing Edge Modification Problems Above Lower Bounds
We study the parameterized complexity of a variant of the F-free Editing problem: Given a graph G and a natural number k, is it possible to modify at most k edges in G so that the resulting graph contains no indu...
-
Article
A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
We study the problem of non-preemptively scheduling n jobs, each job j with a release time \(t_j\) ...
-
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_...
-
Article
Myhill–Nerode Methods for Hypergraphs
We give an analog of the Myhill–Nerode theorem from formal language theory for hypergraphs and use it to derive the following results for two NP-hard hypergraph problems. (1) We provide an algorithm for testin...
-
Article
Interval scheduling and colorful independent sets
Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an integer
-
Article
On the Parameterized Complexity of Computing Balanced Partitions in Graphs
A balanced partition is a clustering of a graph into a given number of equal-sized parts. For instance, the Bisection problem asks to remove at most k edges in order to partition the vertices into two equal-sized...
-
Article
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
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...
