Counting matchings with k unmatched vertices in planar graphs

DOI10.4230/LIPICS.ESA.2016.33MaRDI QIDQ4606302zbMATHFDO

Authors Radu Curticapean

Publication date 2 March 2018

Full work available at URL https://arxiv.org/abs/1607.08192

zbMATH Keywords

parameterized complexityplanar graphscounting complexitymatchings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Counting matchings of size \(k\) is \#W[1]-hard
• The complexity of counting in sparse, regular, and planar graphs
• Weighted counting of \(k\)-matchings is \#W[1]-hard
• On counting perfect matchings in general graphs
• Counting perfect matchings in the geometric dual

Cited in

(1)

• Compactors for parameterized counting problems

This page was built for publication: Counting matchings with \(k\) unmatched vertices in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606302)