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

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 ... 
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 ... 
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 ... 
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 ... 
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 rrank 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 kcyclable 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 viewpoint 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, 20140219)Let F be a family of graphs. In the FCompletion problem, we are given an nvertex 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, 20190906)An undirected graph G is ddegenerate 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 kvertex labeled graph to another kvertex graph. We consider a general family of graph modification problems, called LReplacement to C, where the input is a graph G and ... 
Packing arcdisjoint 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 matrixpartition for loworder 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 Mpartition of G with respect to L is a partition of V(G) into l parts, ... 
Parameterized complexity of conflictfree matchings and paths
(Journal article; Peer reviewed, 2019)An input to a conflictfree variant of a classical problem Gamma, called ConflictFree Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to ConflictFree Gamma in (I,H) ... 
Parameterized kClustering: Tractability Island
(Peer reviewed; Journal article, 2019)In kClustering 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 minones dSAT
(Journal article; Peer reviewed, 2019)In this work, we initiate the study of the MinOnes dSAT problem in the parameterized streaming model. An instance of the problem consists of a dCNF 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 FContraction ...