Efficient algorithms for counting parameterized list H-colorings

Josep Dı́az, Marı́a Serna, Dimitrios M. Thilikos

Type: Article

Publication Date: 2008-02-26

Citations: 7

DOI: https://doi.org/10.1016/j.jcss.2008.02.004

View Publication

Locations

Journal of Computer and System Sciences - View
CiteSeer X (The Pennsylvania State University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings	2004	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+	Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings (Extended Abstract)	2004	Josep D ́ iaz María Serna Dimitrios M. Thilikos
+	Counting list h-colorings and variants	2001	Josep Dı́az María Serna Dimitrios Thilikos Touloupas
+	Fixed-Parameter Tractability of $$(n-k)$$ List Coloring	2019	Aritra Banik Ashwin Jacob Vijay Paliwal Venkatesh Raman
+	Counting Problems in Parameterized Complexity.	2019	Radu Curticapean
+	Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory	2019	Marc Roth Philip Wellnitz
+	Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory	2019	Marc Roth Philip Wellnitz
+	The Complexity of Restrictive H-Coloring	2002	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+	Fixed-Parameter Tractability of (n − k) List Coloring	2020	Aritra Banik Ashwin Jacob Vijay Paliwal Venkatesh Raman
+ PDF Chat	Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory	2019	Marc Roth Philip Wellnitz
+	Complexity issues on bounded restrictive H-coloring	2007	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+	Parameterized Coloring Problems on Threshold Graphs	2019	I. Vinod Reddy
+	The parameterised complexity of counting even and odd induced subgraphs	2014	Mark Jerrum Kitty Meeks
+	The parameterised complexity of counting even and odd induced subgraphs	2014	Mark Jerrum Kitty Meeks
+ PDF Chat	The parameterised complexity of counting even and odd induced subgraphs	2016	Mark Jerrum Kitty Meeks
+ PDF Chat	Some Hard Families of Parameterized Counting Problems	2015	Mark Jerrum Kitty Meeks
+ PDF Chat	Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization	2013	Édouard Bonnet Bruno Escoffier Vangélis Th. Paschos Émeric Tourniaire
+	Parameterized Algorithms for List K-Cycle	2016	Fahad Panolan Meirav Zehavi
+	Parameterized Coloring Problems on Threshold Graphs.	2019	I. Vinod Reddy
+	Multi-parameter complexity analysis for constrained size graph problems: using greediness for parameterization	2013	Édouard Bonnet Bruno Escoffier T H Paschos Vangelis Émeric Tourniaire

Works That Cite This (6)

Action	Title	Year	Authors
+ PDF Chat	Compactors for parameterized counting problems	2021	Dimitrios M. Thilikos
+	In praise of homomorphisms	2021	Pavol Hell Jaroslav Nešetřil
+ PDF Chat	Confronting intractability via parameters	2011	Rodney G. Downey Dimitrios M. Thilikos
+ PDF Chat	Parameterized algorithms for min-max multiway cut and list digraph homomorphism	2017	Eun Jung Kim Christophe Paul Ignasi Sau Dimitrios M. Thilikos
+	Data-compression for Parametrized Counting Problems on Sparse graphs	2018	Eun Jung Kim Marı́a Serna Dimitrios M. Thilikos
+ PDF Chat	Finding small separators in linear time via treewidth reduction	2013	Dáaniel Marx Barry O’Sullivan Igor Razgon

Works Cited by This (8)

Action	Title	Year	Authors
+	Fixed-parameter tractability and completeness III: some structural aspects of the W hierarchy	1993	Rod Downey Michael R. Fellows
+	List Homomorphisms and Circular Arc Graphs	1999	Tomás Feder Pavol Hell Jing Huang
+	The complexity of counting graph homomorphisms	2000	Martin Dyer Catherine Greenhill
+	On the complexity of H-coloring	1990	Pavol Hell Jaroslav Nešetřil
+	CONTRIBUTIONS TO PARAMETERIZED COMPLEXITY	2003	Catherine McCartin
+	Complexity issues on bounded restrictive H-coloring	2007	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+	The Parameterized Complexity of Counting Problems	2004	Jörg Flum Martin Grohe
+ PDF Chat	Corrigendum: The complexity of counting graph homomorphisms	2004	Martin Dyer Catherine Greenhill