1 citations · 1 across the 4 of their papers we have counts for
4 papers
Efficiently Listing Projected Trees, and Equivalence of Listing and Enumeration
Karl Bringmann, Nick Fischer, Yanheng Wang
The subgraph isomorphism problem and its generalizations, such as conjunctive queries where some nodes are projected, are among the most fundamental problems in graph algorithms an…
Touring a Sequence of Orthogonal Polygons
Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist +3
We study the problem of computing a shortest tour that visits a sequence of polygons with a total number of vertices. A tour is an oriented curve such that…
Counting Perfect Matchings in Dense Graphs Is Hard
Nicolas El Maalouly, Yanheng Wang
We show that the problem of counting perfect matchings remains #P-complete even if we restrict the input to very dense graphs, proving the conjecture in [5]. Here "dense graphs" re…
A Perfect Sampler for Hypergraph Independent Sets
Guoliang Qiu, Yanheng Wang, Chihao Zhang
The problem of uniformly sampling hypergraph independent sets is revisited. We design an efficient perfect sampler for the problem under a condition similar to that of the asymmetr…