Batya Kenig

activity

20162025

most citedIntegrity Constraints Revisited: From Exact to Approximate Implication

7 citations · 12 across the 14 of their papers we have counts for

collaborators

Showing cs.DSShow all

5 papers · 1 filter

cs.DS2025

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems

Batya Kenig

Important separators reduce the search space in parameterized graph separation to a small family that can be enumerated efficiently. We extend this approach to cut-uncut problems,…

cs.DS2025

Connectivity-Preserving Minimum Separator in AT-free Graphs

Batya Kenig

Let $A$ and $B$ be disjoint, non-adjacent vertex-sets in an undirected, connected graph $G$ , whose vertices are associated with positive weights. We address the problem of identify…

cs.DS2023

Listing Small Minimal $s, t$ -separators in FPT-Delay

Batya Kenig

Let $G$ be an undirected graph, and $s, t$ distinguished vertices of $G$ . A minimal $s, t$ -separator is an inclusion-wise minimal vertex-set whose removal places $s$ and $t$ in disti…

cs.DS2021

Enumerating Minimal Separators in Ranked Order

Batya Kenig

Let $G$ be an $n$ -vertex graph, and $s, t$ vertices of $G$ . We present an efficient algorithm which enumerates the set of minimal $s t$ -separators of $G$ in ascending order of cardin…

cs.DS2016

Efficiently Enumerating Minimal Triangulations

Nofar Carmeli, Batya Kenig, Benny Kimelfeld +1

We present an algorithm that enumerates all the minimal triangulations of a graph in incremental polynomial time. Consequently, we get an algorithm for enumerating all the proper t…

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems

Connectivity-Preserving Minimum Separator in AT-free Graphs

Listing Small Minimal s,t-separators in FPT-Delay

Enumerating Minimal Separators in Ranked Order

Efficiently Enumerating Minimal Triangulations

Listing Small Minimal $s, t$ -separators in FPT-Delay