Browsing Registrations from Cristin by Journals "Leibniz International Proceedings in Informatics"
Now showing items 120 of 47

A (2 + ε)Factor Approximation Algorithm for Split Vertex Deletion
(Journal article; Peer reviewed, 2020)In the Split Vertex Deletion (SVD) problem, the input is an nvertex undirected graph G and a weight function w: V(G) → ℕ, and the objective is to find a minimum weight subset S of vertices such that GS is a split graph ... 
An Algorithmic MetaTheorem for Graph Modification to Planarity and FOL
(Journal article; Peer reviewed, 2020)In general, a graph modification problem is defined by a graph modification operation ⊠ and a target graph property 𝒫. Typically, the modification operation ⊠ may be vertex removal, edge removal, edge contraction, or edge ... 
Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
(Journal article; Peer reviewed, 2020)Given a vertexcolored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertexconnected if there is a rainbow vertex path between every pair of its ... 
Approximation in (poly) logarithmic space
(Journal article; Peer reviewed, 2020)We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d–Hitting Set that runs in time nO(d2+(d/ε)), ... 
bColoring Parameterized by CliqueWidth
(Journal article; Peer reviewed, 2021)We provide a polynomialtime algorithm for bColoring on graphs of constant cliquewidth. This unifies and extends nearly all previously known polynomialtime results on graph classes, and answers open questions posed by ... 
Bisection of Bounded Treewidth Graphs by Convolutions
(Journal article; Peer reviewed, 2019)In the Bisection problem, we are given as input an edgeweighted graph G. The task is to find a partition of V(G) into two parts A and B such that A  B <= 1 and the sum of the weights of the edges with one endpoint ... 
Building large kcores from sparse graphs
(Journal article; Peer reviewed, 2020)A popular model to measure network stability is the kcore, that is the maximal induced subgraph in which every vertex has degree at least k. For example, kcores are commonly used to model the unraveling phenomena in ... 
Close Relatives of Feedback Vertex Set Without SingleExponential Algorithms Parameterized by Treewidth
(Journal article; Peer reviewed, 2020)The Cut & Count technique and the rankbased approach have lead to singleexponential FPT algorithms parameterized by treewidth, that is, running in time 2^𝒪(tw)n^𝒪(1), for Feedback Vertex Set and connected versions of ... 
CoDegeneracy and CoTreewidth: Using the Complement to Solve Dense Instances
(Journal article; Peer reviewed, 2021)Cliquewidth and treewidth are two of the most important and useful graph parameters, and several problems can be solved efficiently when restricted to graphs of bounded cliquewidth or treewidth. Bounded treewidth implies ... 
Coherence for Monoidal Groupoids in HoTT
(Journal article; Peer reviewed, 2020)We present a proof of coherence for monoidal groupoids in homotopy type theory. An important role in the formulation and in the proof of coherence is played by groupoids with a free monoidal structure; these can be represented ... 
Complexity of the Steiner Network Problem with Respect to the Number of Terminals
(Journal article; Peer reviewed, 2019)In the Directed Steiner Network problem we are given an arcweighted digraph G, a set of terminals T subseteq V(G) with T=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H ... 
Compressing permutation groups into grammars and polytopes. A graph embedding approach
(Journal article; Peer reviewed, 2020)It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+G) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can ... 
Connecting the Dots (with Minimum Crossings)
(Journal article; Peer reviewed, 2019)We study a prototype Crossing Minimization problem, defined as follows. Let F be an infinite family of (possibly vertexlabeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection ... 
Diverse Collections in Matroids and Graphs
(Journal article; Peer reviewed, 2021)We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the Weighted Diverse ... 
Diverse Pairs of Matchings
(Journal article; Peer reviewed, 2020)We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse ... 
ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space
(Journal article; Peer reviewed, 2021)De Berg et al. in [SICOMP 2020] gave an algorithmic framework for subexponential algorithms on geometric graphs with tight (up to ETH) running times. This framework is based on dynamic programming on graphs of weighted ... 
ETHtight algorithms for long path and cycle on unit disk graphs
(Journal article; Peer reviewed, 2020)We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2O(√k)(n + m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs ... 
Exact and approximate digraph bandwidth
(Journal article; Peer reviewed, 2019)In this paper, we introduce a directed variant of the classical Bandwidth problem and study it from the viewpoint of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of ... 
Fault tolerant subgraphs with applications in kernelization
(Journal article; Peer reviewed, 2020)In the past decade, the design of fault tolerant data structures for networks has become a central topic of research. Particular attention has been given to the construction of a subgraph H of a given digraph D with as ... 
Hierarchical clusterings of unweighted graphs
(Journal article; Peer reviewed, 2020)We study the complexity of finding an optimal hierarchical clustering of an unweighted similarity graph under the recently introduced Dasgupta objective function. We introduce a proof technique, called the normalization ...