Blar i Bergen Open Research Archive på tidsskrift "Leibniz International Proceedings in Informatics"
Viser treff 1-19 av 19
-
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 ... -
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 n-vertex graph G, an integer k, and ... -
A complexity dichotomy for critical values of the b-chromatic number of graphs
(Peer reviewed; Journal article, 2019-08-20)A b-coloring 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 b-Coloring 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 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 ... -
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 ... -
Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals
(Peer reviewed; Journal article, 2019)Perturbed graphic matroids are binary matroids that can be obtained from a graphic matroid by adding a noise of small rank. More precisely, an r-rank perturbed graphic matroid M is a binary matroid that can be represented ... -
Cyclability in Graph Classes
(Peer reviewed; Journal article, 2019)A subset T subseteq V(G) of vertices of a graph G is said to be cyclable if G has a cycle C containing every vertex of T, and for a positive integer k, a graph G is k-cyclable if every subset of vertices of G of size at ... -
Decomposition of map graphs with applications
(Peer reviewed; Journal article, 2019) -
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 view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of ... -
Exploring Subexponential Parameterized Complexity of Completion Problems
(Peer reviewed; Journal article, 2014-02-19)Let F be a family of graphs. In the F-Completion problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k edges can be added to G so that the resulting graph does not contain a graph ... -
Going Far From Degeneracy
(Peer reviewed; Journal article, 2019-09-06)An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erd\H{o}s and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least ... -
A Model of Type Theory in Cubical Sets
(Peer reviewed; Journal article, 2014)We present a model of type theory with dependent product, sum, and identity, in cubical sets. We describe a universe and explain how to transform an equivalence between two types into an equality. We also explain how to ... -
Modification to planarity is fixed parameter tractable
(Peer reviewed; Journal article, 2019)A replacement action is a function L that maps each k-vertex labeled graph to another k-vertex graph. We consider a general family of graph modification problems, called L-Replacement to C, where the input is a graph G and ... -
Packing arc-disjoint cycles in tournaments
(Journal article; Peer reviewed, 2019)A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining ... -
Parameterized complexity classification of deletion to list matrix-partition for low-order matrices
(Journal article; Peer reviewed, 2019)Given a symmetric l x l matrix M=(m_{i,j}) with entries in {0,1,*}, a graph G and a function L : V(G) - > 2^{[l]} (where [l] = {1,2,...,l}), a list M-partition of G with respect to L is a partition of V(G) into l parts, ... -
Parameterized complexity of conflict-free matchings and paths
(Journal article; Peer reviewed, 2019)An input to a conflict-free variant of a classical problem Gamma, called Conflict-Free Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to Conflict-Free Gamma in (I,H) ... -
Parameterized k-Clustering: Tractability Island
(Peer reviewed; Journal article, 2019)In k-Clustering we are given a multiset of n vectors X subset Z^d and a nonnegative number D, and we need to decide whether X can be partitioned into k clusters C_1, ..., C_k such that the cost sum_{i=1}^k min_{c_i in R^d} ... -
Parameterized streaming algorithms for min-ones d-SAT
(Journal article; Peer reviewed, 2019)In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has ... -
Path Contraction Faster Than 2n
(Peer reviewed; Journal article, 2019)A graph G is contractible to a graph H if there is a set X subseteq E(G), such that G/X is isomorphic to H. Here, G/X is the graph obtained from G by contracting all the edges in X. For a family of graphs F, the F-Contraction ...