research
∙
07/17/2023
Hypergraph Splitting-off and Covering Skew-Supermodular Functions in Strongly Polynomial Time
We consider hypergraph network design problems where the goal is to cons...
share
research
∙
05/01/2023
Approximating submodular k-partition via principal partition sequence
In submodular k-partition, the input is a non-negative submodular functi...
research
∙
03/22/2023
Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
We consider the feedback vertex set problem in undirected graphs (FVS). ...
research
∙
11/30/2022
Approximate minimum cuts and their enumeration
We show that every α-approximate minimum cut in a connected graph is the...
research
∙
04/20/2022
Counting and enumerating optimum cut sets for hypergraph k-partitioning problems for fixed k
We consider the problem of enumerating optimal solutions for two hypergr...
research
∙
10/27/2021
Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k
We consider the problem of deterministically enumerating all minimum k-c...
research
∙
10/01/2021
Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree
A heapable sequence is a sequence of numbers that can be arranged in a "...
research
∙
06/28/2021
ℓ_p-norm Multiway Cut
We introduce and study ℓ_p-norm-multiway-cut: the input here is an undir...
research
∙
11/16/2020
Faster connectivity in low-rank hypergraphs via expander decomposition
We design an algorithm for computing connectivity in hypergraphs which r...
research
∙
11/06/2020
Fixed Parameter Approximation Scheme for Min-max k-cut
We consider the graph k-partitioning problem under the min-max objective...
research
∙
09/25/2020
Hypergraph k-cut for fixed k in deterministic polynomial time
We consider the Hypergraph-k-cut problem. The input consists of a hyperg...
research
∙
06/20/2020
Multicritera Cuts and Size-Constrained k-cuts in Hypergraphs
We address counting and optimization variants of multicriteria global mi...
research
∙
09/17/2019
The Maximum Binary Tree Problem
We introduce and investigate the approximability of the maximum binary t...
research
∙
07/25/2018
Improving the Integrality Gap for Multiway Cut
In the multiway cut problem, we are given an undirected graph with non-n...
research
∙
07/16/2018
Improving the smoothed complexity of FLIP for max cut problems
Finding locally optimal solutions for max-cut and max-k-cut are well-kno...
research
∙
12/22/2017
