39 citations · 193 across the 19 of their papers we have counts for
22 papers
A Markov chain on the solution space of edge-colorings of bipartite graphs
Letong Hong, Istvan Miklos
In this paper, we exhibit an irreducible Markov chain on the edge -colorings of bipartite graphs based on certain properties of the solution space. We show that diameter of…
#P-hardness proofs of matrix immanants evaluated on restricted matrices
Istvan Miklos, Cordian Riener
We establish the -hardness of computing a broad class of immanants, even when restricted to specific categories of matrices. Concretely, we prove that computing -immanants…
Counting Maximum Matchings in Planar Graphs Is Hard
Istvan Miklos, Miklos Kresz
Here we prove that counting maximum matchings in planar, bipartite graphs is #P-complete. This is somewhat surprising in the light that the number of perfect matchings in planar gr…
Efficiently sampling the realizations of irregular, but linearly bounded bipartite and directed degree sequences
Péter L. Erdős, Tamás Róbert Mezei, István Miklós
Since 1997 a considerable effort has been spent on the study of the swap (switch) Markov chains on graphic degree sequences. Several results were proved on rapidly mixing Markov ch…
Packing tree degree sequences
Aravind Gollakota, William Hardt, Istvan Miklos
We consider packing tree degree sequences in this paper. We set up a conjecture that any arbitrary number of tree degree sequences without common leaves have edge disjoint tree rea…
Not all simple looking degree sequence problems are easy
Péter L. Erdős, István Miklós
Degree sequence (DS) problems are around for at least hundred twenty years, and with the advent of network science, more and more complicated, structured DS problems were invented.…