×

Counting the number of matchings in chordal and chordal bipartite graph classes. (English) Zbl 1273.05180

Paul, Christophe (ed.) et al., Graph-theoretic concepts in computer science. 35th international workshop, WG 2009, Montpellier, France, June 24–26, 2009. Revised papers. Berlin: Springer (ISBN 978-3-642-11408-3/pbk). Lecture Notes in Computer Science 5911, 296-307 (2010).
Summary: We provide polynomial-time algorithms for counting the number of perfect matchings in chain graphs, cochain graphs, and threshold graphs. These algorithms are based on newly developed subdivision schemes that we call a recursive decomposition. On the other hand, we show the \(\#\mathrm{P}\)-completeness for counting the number of perfect matchings in chordal graphs, split graphs and chordal bipartite graphs. This is in an interesting contrast with the fact that counting the number of independent sets in chordal graphs can be done in linear time.
For the entire collection see [Zbl 1179.68005].

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C30 Enumeration in graph theory
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI