Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width

DOI10.1007/978-3-642-20877-5_47zbMath1333.05291arXiv1806.00791OpenAlexW1540768932MaRDI QIDQ3010427

Takeaki Uno, Benjamin Hellouin de Menibus

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

countingmaximal matchingclique-widthpath matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Counting the number of independent sets in chordal graphs
• Distance-hereditary graphs
• Approximating the permanent of graphs with large factors
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Clique-width minimization is NP-hard
• Easy problems for tree-decomposable graphs
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• The Complexity of Enumeration and Reliability Problems
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On the Relationship Between Clique-Width and Treewidth
• Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width