Counting the number of matchings in chordal and chordal bipartite graph classes

DOI10.1007/978-3-642-11409-0_26MaRDI QIDQ5851114zbMATH OpenOpenAlexFDO

Authors Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno

Publication date 21 January 2010

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-11409-0_26

Mathematics Subject Classification ID

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

Recommendations

• On counting perfect matchings in general graphs
• Counting the number of independent sets in chordal graphs
• Graph-Theoretic Concepts in Computer Science
• The number of perfect matchings in three types of graphs
• The number of perfect matchings of two types of particular graphs

Cited in

(13)

• Alternating cycle-free matchings
• Chip removal for computing the number of perfect matchings
• Solving matching problems efficiently in bipartite graphs
• Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• scientific article; zbMATH DE number 2080986 (Why is no real title available?)
• Enumeration of Matchings in the Incidence Graphs of Complete and Complete Bipartite Graphs
• Counting perfect matchings and the switch chain
• Graph classes and the switch Markov chain for matchings
• Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs
• Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
• On the exact matching problem in dense graphs
• On listing, sampling, and counting the chordal graphs with edge constraints

This page was built for publication: Counting the number of matchings in chordal and chordal bipartite graph classes

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