Efficient algorithms for counting parameterized list \(H\)-colorings

DOI10.1016/J.JCSS.2008.02.004zbMath1160.68024OpenAlexW2112022679MaRDI QIDQ931733

Dimitrios M. Thilikos, Josep Diaz, Maria J. Serna

Publication date: 26 June 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2008.02.004

zbMATH Keywords

parameterizationcounting problemsrestrictive \(H\)-coloringrestrictive list \(H\)-coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Compactors for parameterized counting problems ⋮ In praise of homomorphisms ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Confronting intractability via parameters ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Finding odd cycle transversals.
• List homomorphisms to reflexive graphs
• The restrictive \(H\)-coloring problem
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• List homomorphisms and circular arc graphs
• Complexity issues on bounded restrictive \(H\)-coloring
• Corrigendum: The complexity of counting graph homomorphisms
• Nondeterminism within $P^ * $
• The Parameterized Complexity of Counting Problems
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Algorithms and Data Structures
• Algorithms – ESA 2004

This page was built for publication: Efficient algorithms for counting parameterized list \(H\)-colorings