Blar i Bergen Open Research Archive på forfatter "Bentert, Matthias"

Viser treff 1-5 av 5

    • Breaking a Graph into Connected Components with Small Dominating Sets 

      Bentert, Matthias; Fellows, Michael R.; Golovach, Petr; Rosamond, Frances; Saurabh, Saket (Journal article; Peer reviewed, 2024)
      We study DOMINATED CLUSTER DELETION. Therein, we are given an undirected graph G = (V,E) and integers k and d and the task is to find a set of at most k vertices such that removing these vertices results in a graph in which ...

    • Cluster Editing with Overlapping Communities 

      Arrighi, Emmanuel Jean Paul Pierre; Bentert, Matthias; Drange, Pål Grønås; Sullivan, Blair D.; Wolf, Petra Henrike Karola (Journal article; Peer reviewed, 2023)
      Cluster Editing, also known as correlation clustering, is a well-studied graph modification problem. In this problem, one is given a graph and allowed to perform up to k edge additions and deletions to transform it into a ...

    • Correlation Clustering with Vertex Splitting 

      Bentert, Matthias; Crane, Alex; Drange, Pål Grønås; Reidl, Felix; Sullivan, Blair D. (Journal article; Peer reviewed, 2024)
      We explore CLUSTER EDITING and its generalization CORRELATION CLUSTERING with a new operation called permissive vertex splitting which addresses finding overlapping clusters in the face of uncertain information. We determine ...

    • PACE Solver Description: LUNCH - Linear Uncrossing Heuristics 

      Langedal, Kenneth; Bentert, Matthias; Blanco, Thorgal; Drange, Pål Grønås (Journal article; Peer reviewed, 2024)
      The 2024 PACE challenge is on One-Sided Crossing Minimization: Given a bipartite graph with one fixed and one free layer, compute an ordering of the vertices in the free layer that minimizes the number of edge crossings ...

    • Two-Sets Cut-Uncut on Planar Graphs 

      Bentert, Matthias; Drange, Pål Grønås; Fomin, Fedor; Golovach, Petr; Korhonen, Tuukka (Journal article; Peer reviewed, 2024)
      We study Two-Sets Cut-Uncut on planar graphs. Therein, one is given an undirected planar graph G and two disjoint sets S and T of vertices as input. The question is, what is the minimum number of edges to remove from G, ...