Approximately counting perfect matchings in general graphs

Martin Fürer; Shiva Prasad Kasiviswanathan

Approximately counting perfect matchings in general graphs

Martin Fürer, Shiva Prasad Kasiviswanathan

Eberly College of Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Scopus citations

Abstract

So far only one approximation algorithm for the number of perfect matchings in general graphs is known. This algorithm of Chien [2] is based on determinants. We present a much simpler algorithm together with some of its variants. One of them has an excellent performance for random graphs, another one might be a candidate for a good worst case performance. We also present an experimental analysis of one of our algorithms.

Original language	English (US)
Title of host publication	Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics
Editors	C. Demetrescu, R. Sedgewick, R. Tamassia
Pages	263-272
Number of pages	10
State	Published - 2005
Event	Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics - Vancouver, BC, Canada Duration: Jan 22 2005 → Jan 22 2005

Publication series

Name	Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics

Other

Other	Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics
Country/Territory	Canada
City	Vancouver, BC
Period	1/22/05 → 1/22/05

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

Fürer, M., & Kasiviswanathan, S. P. (2005). Approximately counting perfect matchings in general graphs. In C. Demetrescu, R. Sedgewick, & R. Tamassia (Eds.), Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics (pp. 263-272). (Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics).

Fürer, Martin ; Kasiviswanathan, Shiva Prasad. / Approximately counting perfect matchings in general graphs. Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics. editor / C. Demetrescu ; R. Sedgewick ; R. Tamassia. 2005. pp. 263-272 (Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics).

@inproceedings{9e4c4dfe9be74f89a809ba10c295cbd6,

title = "Approximately counting perfect matchings in general graphs",

abstract = "So far only one approximation algorithm for the number of perfect matchings in general graphs is known. This algorithm of Chien [2] is based on determinants. We present a much simpler algorithm together with some of its variants. One of them has an excellent performance for random graphs, another one might be a candidate for a good worst case performance. We also present an experimental analysis of one of our algorithms.",

author = "Martin F{\"u}rer and Kasiviswanathan, {Shiva Prasad}",

year = "2005",

language = "English (US)",

isbn = "0898715962",

series = "Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics",

pages = "263--272",

editor = "C. Demetrescu and R. Sedgewick and R. Tamassia",

booktitle = "Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics",

note = "Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics ; Conference date: 22-01-2005 Through 22-01-2005",

}

Fürer, M & Kasiviswanathan, SP 2005, Approximately counting perfect matchings in general graphs. in C Demetrescu, R Sedgewick & R Tamassia (eds), Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics. Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics, pp. 263-272, Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics, Vancouver, BC, Canada, 1/22/05.

Approximately counting perfect matchings in general graphs. / Fürer, Martin; Kasiviswanathan, Shiva Prasad.
Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics. ed. / C. Demetrescu; R. Sedgewick; R. Tamassia. 2005. p. 263-272 (Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Approximately counting perfect matchings in general graphs

AU - Fürer, Martin

AU - Kasiviswanathan, Shiva Prasad

PY - 2005

Y1 - 2005

N2 - So far only one approximation algorithm for the number of perfect matchings in general graphs is known. This algorithm of Chien [2] is based on determinants. We present a much simpler algorithm together with some of its variants. One of them has an excellent performance for random graphs, another one might be a candidate for a good worst case performance. We also present an experimental analysis of one of our algorithms.

AB - So far only one approximation algorithm for the number of perfect matchings in general graphs is known. This algorithm of Chien [2] is based on determinants. We present a much simpler algorithm together with some of its variants. One of them has an excellent performance for random graphs, another one might be a candidate for a good worst case performance. We also present an experimental analysis of one of our algorithms.

UR - http://www.scopus.com/inward/record.url?scp=32144464574&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=32144464574&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:32144464574

SN - 0898715962

SN - 9780898715965

T3 - Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics

SP - 263

EP - 272

BT - Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics

A2 - Demetrescu, C.

A2 - Sedgewick, R.

A2 - Tamassia, R.

T2 - Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics

Y2 - 22 January 2005 through 22 January 2005

ER -

Fürer M, Kasiviswanathan SP. Approximately counting perfect matchings in general graphs. In Demetrescu C, Sedgewick R, Tamassia R, editors, Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics. 2005. p. 263-272. (Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics).

Approximately counting perfect matchings in general graphs

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this