Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
From MaRDI portal
Publication:3010427
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
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