Blar i Registrations from Cristin på tidsskrift "Leibniz International Proceedings in Informatics"
Viser treff 21-40 av 66
-
ETH-Tight Algorithms for Finding Surfaces in Simplicial Complexes of Bounded Treewidth
(Journal article; Peer reviewed, 2022)Given a simplicial complex with n simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected surface with a fixed boundary. We also study ... -
ETH-tight algorithms for long path and cycle on unit disk graphs
(Journal article; Peer reviewed, 2020)We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2O(√k)(n + m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs ... -
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 ... -
Exact Exponential Algorithms for Clustering Problems
(Journal article; Peer reviewed, 2022)In this paper we initiate a systematic study of exact algorithms for some of the well known clustering problems, namely k-MEDIAN and k-MEANS. In k-MEDIAN, the input consists of a set X of n points belonging to a metric ... -
Fault tolerant subgraphs with applications in kernelization
(Journal article; Peer reviewed, 2020)In the past decade, the design of fault tolerant data structures for networks has become a central topic of research. Particular attention has been given to the construction of a subgraph H of a given digraph D with as ... -
FPT Approximation for Fair Minimum-Load Clustering
(Journal article; Peer reviewed, 2022)In this paper, we consider the Minimum-Load k-Clustering/Facility Location (MLkC) problem where we are given a set P of n points in a metric space that we have to cluster and an integer k > 0 that denotes the number of ... -
Hierarchical clusterings of unweighted graphs
(Journal article; Peer reviewed, 2020)We study the complexity of finding an optimal hierarchical clustering of an unweighted similarity graph under the recently introduced Dasgupta objective function. We introduce a proof technique, called the normalization ... -
Kernelization of Whitney Switches
(Journal article; Peer reviewed, 2020)A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs G and H are 2-isomorphic, or equivalently, their cycle matroids are isomorphic, if and only if G can be transformed into H by a series of operations ... -
Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms
(Journal article; Peer reviewed, 2022)We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree ... -
Longest Cycle Above Erdös-Gallai Bound
(Journal article; Peer reviewed, 2022)In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2^𝒪(k)⋅n^𝒪(1) decides whether a 2-connected ... -
Low-Rank Binary Matrix Approximation in Column-Sum Norm
(Journal article; Peer reviewed, 2020)We consider 𝓁₁-Rank-r Approximation over {GF}(2), where for a binary m× n matrix 𝐀 and a positive integer constant r, one seeks a binary matrix 𝐁 of rank at most r, minimizing the column-sum norm ‖ 𝐀 -𝐁‖₁. We show ... -
Non-Uniform k-Center and Greedy Clustering
(Journal article; Peer reviewed, 2022)In the Non-Uniform k-Center (NUkC) problem, a generalization of the famous k-center clustering problem, we want to cover the given set of points in a metric space by finding a placement of balls with specified radii. In ... -
On the Complexity of Intersection Non-emptiness for Star-Free Language Classes
(Journal article; Peer reviewed, 2021)In the Intersection Non-emptiness problem, we are given a list of finite automata A_1, A_2,… , A_m over a common alphabet Σ as input, and the goal is to determine whether some string w ∈ Σ^* lies in the intersection of the ... -
On the Complexity of Recovering Incidence Matrices
(Journal article; Peer reviewed, 2020)The incidence matrix of a graph is a fundamental object naturally appearing in many applications, involving graphs such as social networks, communication networks, or transportation networks. Often, the data collected about ... -
On the Hardness of Generalized Domination Problems Parameterized by Mim-Width
(Journal article; Peer reviewed, 2022)For nonempty σ, ρ ⊆ ℕ, a vertex set S in a graph G is a (σ, ρ)-dominating set if for all v ∈ S, |N(v) ∩ S| ∈ σ, and for all v ∈ V(G) ⧵ S, |N(v) ∩ S| ∈ ρ. The Min/Max (σ,ρ)-Dominating Set problems ask, given a graph G and ... -
On the parameterized complexity of deletion to H-free strong components
(Journal article; Peer reviewed, 2020)Directed Feedback Vertex Set (DFVS) is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the study of a wide generalization, the H-SCC Deletion ... -
On the Satisfiability of Smooth Grid CSPs
(Journal article; Peer reviewed, 2022)Many important NP-hard problems, arising in a wide variety of contexts, can be reduced straightforwardly to the satisfiability problem for CSPs whose underlying graph is a grid. In this work, we push forward the study of ... -
Order Reconfiguration Under Width Constraints
(Journal article; Peer reviewed, 2021)In this work, we consider the following order reconfiguration problem: Given a graph G together with linear orders ω and ω' of the vertices of G, can one transform ω into ω' by a sequence of swaps of adjacent elements in ... -
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 ... -
Parameterization Above a Multiplicative Guarantee
(Journal article; Peer reviewed, 2020)Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given ...