Counting edge-injective homomorphisms and matchings on restricted graph classes
We consider the #W[1]-hard problem of counting all matchings with exactly k edges in a given input graph G; we prove that it remains #W[1]-hard on graphs G that are line graphs or bipartite graphs with degree 2 on one side. In our proofs, we use that k-matchings in line graphs can be equivalently vi...
| Huvudupphovsmän: | , , |
|---|---|
| Materialtyp: | Journal article |
| Språk: | English |
| Publicerad: |
Springer Nature
2018
|
Search Result 1
Counting edge-injective homomorphisms and matchings on restricted graph classes
Publicerad 2017
Conference item