Blar i Bergen Open Research Archive på tidsskrift "Leibniz International Proceedings in Informatics"
Viser treff 120 av 97

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 ... 
Approximating Acyclicity Parameters of Sparse Hypergraphs
(Peer reviewed; Journal article, 2009)The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized ... 
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/ε)), ... 
Bchromatic number: Beyond NPhardness
(Peer reviewed; Journal article, 2015)The bchromatic number of a graph G, chi_b(G), is the largest integer k such that G has a kvertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other ... 
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 ... 
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 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 ... 
Clustering to Given Connectivities
(Peer reviewed; Journal article, 2019)We define a general variant of the graph clustering problem where the criterion of density for the clusters is (high) connectivity. In Clustering to Given Connectivities, we are given an nvertex graph G, an integer k, and ... 
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 ... 
A complexity dichotomy for critical values of the bchromatic number of graphs
(Peer reviewed; Journal article, 20190820)A bcoloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The bColoring problem asks whether a graph G has ... 
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 ... 
Computing cutwidth and pathwidth of semicomplete digraphs via degree orderings
(Peer reviewed; Journal article, 2013)The notions of cutwidth and pathwidth of digraphs play a central role in the containment theory for tournaments, or more generally semicomplete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, ... 
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 ... 
Connecting Vertices by Independent Trees
(Journal article; Peer reviewed, 2014)We study the paramereteized complexity of the following connectivity problem. For a vertex subset U of a graph G, trees T1, . . . , Ts of G are completely independent spanning trees of U if each of them contains U , and ...