Blar i University of Bergen Library på tidsskrift "Algorithmica"
Viser treff 1-8 av 8
-
Metric Dimension Parameterized By Treewidth
(Journal article; Peer reviewed, 2021)A resolving set S of a graph G is a subset of its vertices such that no two vertices of G have the same distance vector to S. The METRIC DIMENSION problem asks for a resolving set of minimum size, and in its decision form, ... -
Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-Width
(Journal article; Peer reviewed, 2022)The two weighted graph problems Node Multiway Cut (NMC) and Subset Feedback Vertex Set (SFVS) both ask for a vertex set of minimum total weight, that for NMC disconnects a given set of terminals, and for SFVS intersects ... -
On Perturbation Resilience of Non-uniform k-Center
(Journal article; Peer reviewed, 2021)The Non-Uniform k-center (NUkC) problem has recently been formulated by Chakrabarty et al. [ICALP, 2016; ACM Trans Algorithms 16(4):46:1–46:19, 2020] as a generalization of the classical k-center clustering problem. In ... -
On the Tractability of Optimization Problems on H-Graphs
(Journal article; Peer reviewed, 2020)For a graph H, a graph G is an H-graph if it is an intersection graph of connected subgraphs of some subdivision of H. H-graphs naturally generalize several important graph classes like interval graphs or circular-arc ... -
Parameterized Complexity of Directed Spanner Problems
(Journal article; Peer reviewed, 2021)We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance ... -
Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs
(Journal article; Peer reviewed, 2021)We study algorithmic properties of the graph class CHORDAL−ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fll-in at most k. It appears that a ... -
Subgraph Complementation
(Journal article; Peer reviewed, 2020-02)A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class G, is there ... -
Towards a Polynomial Kernel for Directed Feedback Vertex Set
(Journal article; Peer reviewed, 2020)In the DIRECTED FEEDBACK VERTEX SET (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. ...