Authors
Citation
Sh. Teng, INDEPENDENT SETS VERSUS PERFECT MATCHINGS, Theoretical computer science, 145(1-2), 1995, pp. 381-390
Citations number
13
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
ISSN journal
03043975
Volume
145
Issue
1-2
Year of publication
1995
Pages
381 - 390
Database
ISI
SICI code
0304-3975(1995)145:1-2<381:ISVPM>2.0.ZU;2-X
Abstract
Some structural relationships between matchings and independent sets a
re presented. One consequence is that any NC algorithm for generating
a uniform random perfect matching of a bipartite graph must differ fro
m the only known polynomial time random matching algorithm, due to Bro
der (1986) and Jerrum and Sinclair (1988), unless NC = P. Efficient pa
rallel algorithms for emulating random walk on general graphs and some
implicitly represented large-scale graphs are also presented.