49 citations · 228 across the 16 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2008★ 6 cited
A randomized polynomial-time algorithm for the Spanning Hypertree Problem on 3-uniform hypergraphs
Sergio Caracciolo, Gregor Masbaum, Alan D. Sokal +1
Consider the problem of determining whether there exists a spanning hypertree in a given k-uniform hypergraph. This problem is trivially in P for k=2, and is NP-complete for k>= 4,…
cs.CC2006
One-in-Two-Matching Problem is NP-complete
Sergio Caracciolo, Davide Fichera, Andrea Sportiello
2-dimensional Matching Problem, which requires to find a matching of left- to right-vertices in a balanced -vertex bipartite graph, is a well-known polynomial problem, while va…