3 papers
cs.DS2026
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…
cs.CG2026
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…
cs.DS2022
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…