3 citations · 8 across the 9 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.DS2017
The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern
Robert Krauthgamer, Ohad Trabelsi
In the Set Cover problem, the input is a ground set of elements and a collection of sets, and the goal is to find the smallest sub-collection of sets whose union is the ent…
cs.DS2017★ 3 cited
Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern
Robert Krauthgamer, Ohad Trabelsi
The kTree problem is a special case of Subgraph Isomorphism where the pattern graph is a tree, that is, the input is an -node graph and a -node tree , and the goal is…
cs.DS2017
Conditional Lower Bounds for All-Pairs Max-Flow
Robert Krauthgamer, Ohad Trabelsi
We provide evidence that computing the maximum flow value between every pair of nodes in a directed graph on nodes, edges,and capacities in the range , which we cal…