Search for Author All Reviews
	Jerrum, Mark     Options: All Media Types Journals Proceedings Div Books Whole Books Other Date Reviewed Title Author Publisher Published Date Descending Ascending Date Reviewed     1 - 4 of 4 reviews       A complexity trichotomy for approximately counting list H-colorings Galanis A., Goldberg L., Jerrum M. ACM Transactions on Computation Theory 9(2): 1-22, 2017.  Type: Article H-colorings are essential in the exploration of language syntax expositions. An H-coloring is the allocation of adjacent colors to neighboring vertices of a graph G. An ...... Jan 11 2018     A bound on the capacity of backoff and acknowledgment-based protocols Goldberg L., Jerrum M., Kannan S., Paterson M. SIAM Journal on Computing 33(2): 313-331, 2004.  Type: Article In an acknowledgment-based protocol, the probability that a message is sent over the link depends only on its past transmission history. In each time slot, at most one send is allowed; more than one is known as a collision....... Apr 21 2004     A polynomial algorithm for deciding bisimilarity of normed context-free processes Hirshfeld Y., Jerrum M., Moller F. (ed) Theoretical Computer Science 158(1-2): 143-159, 1996.  Type: Article Process algebra is an algebraic formalism for specifying and reasoning about concurrent systems. The basic notion of equivalence among processes in such formalisms is that of bisimilarity. Bisimilarity is in general undecidable, but fo...... Oct 1 1997     The complexity of finding minimum-length generator sequences Jerrum M. Theoretical Computer Science 36(2-3): 265-289, 1985.  Type: Article Any set of permutations generates a permutation group. How difficult is it to determine if a target permutation is in this group? Furst, Hopcroft, and Luks [1] have shown that this problem can be solved in time polynomial in the number...... May 1 1986
	Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud® Terms of Use | Privacy Policy