Blar i Registrations from Cristin på tidsskrift "Leibniz International Proceedings in Informatics"
Viser treff 1-20 av 66
-
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 n-vertex 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 G-S is a split graph ... -
An Algorithmic Meta-Theorem 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 vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected 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/ε)), ... -
b-Coloring Parameterized by Clique-Width
(Journal article; Peer reviewed, 2021)We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial-time 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 edge-weighted 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 k-cores from sparse graphs
(Journal article; Peer reviewed, 2020)A popular model to measure network stability is the k-core, that is the maximal induced subgraph in which every vertex has degree at least k. For example, k-cores are commonly used to model the unraveling phenomena in ... -
Classes of Intersection Digraphs with Good Algorithmic Properties
(Journal article; Peer reviewed, 2022)While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions ... -
Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth
(Journal article; Peer reviewed, 2020)The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time 2^𝒪(tw)n^𝒪(1), for Feedback Vertex Set and connected versions of ... -
Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances
(Journal article; Peer reviewed, 2021)Clique-width 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 clique-width 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 arc-weighted 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 vertex-labeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection ... -
Detours in Directed Graphs
(Journal article; Peer reviewed, 2022)We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, ... -
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 ... -
Dynamic Programming on Bipartite Tree Decompositions
(Journal article; Peer reviewed, 2023)We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of ... -
Efficient Minimum Weight Vertex Cover Heuristics Using Graph Neural Networks
(Journal article; Peer reviewed, 2022)Minimum weighted vertex cover is the NP-hard graph problem of choosing a subset of vertices incident to all edges such that the sum of the weights of the chosen vertices is minimum. Previous efforts for solving this in ... -
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 ...