The Library
On counting homomorphisms to directed acyclic graphs
Tools
Tools
Tools
Dyer, Martin, Goldberg, Leslie Ann and Paterson, Mike (2006) On counting homomorphisms to directed acyclic graphs. In: 33rd International Colloquium on Automata, Languages and Programming, Venice, ITALY, JUL 10-14, 2006. Published in: AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1, 4051 pp. 38-49.
Full text not available from this repository.Abstract
We give a dichotomy theorem for the problem of counting homomorphisms to directed acyclic graphs. H is a fixed directed acyclic graph. The problem is, given an input digraph G, to determine how many homomorphisms there are from G to H. We give a graph-theoretic classification, showing that for some digraphs H, the problem is in P and for the rest of the digraphs H the problem is #P-complete. An interesting feature of the dichotomy, absent from related dichotomy results, is the rich supply of tractable graphs H with complex structure.
| Item Type: | Conference Item (UNSPECIFIED) |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Series Name: | LECTURE NOTES IN COMPUTER SCIENCE |
| Journal or Publication Title: | AUTOMATA, LANGUAGES AND PROGRAMMING, PT 1 |
| Publisher: | SPRINGER-VERLAG BERLIN |
| ISBN: | 3-540-35904-4 |
| ISSN: | 0302-9743 |
| Editor: | Bugliesi, M and Preneel, B and Sassone, V and Wegener, I |
| Date: | 2006 |
| Volume: | 4051 |
| Number of Pages: | 12 |
| Page Range: | pp. 38-49 |
| Identification Number: | 10.1007/11786986_5 |
| Publication Status: | Published |
| Title of Event: | 33rd International Colloquium on Automata, Languages and Programming |
| Location of Event: | Venice, ITALY |
| Date(s) of Event: | JUL 10-14, 2006 |
| URI: | http://wrap.warwick.ac.uk/id/eprint/33158 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
