Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings

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

Type: Book-Chapter

Publication Date: 2004-01-01

Citations: 7

DOI: https://doi.org/10.1007/978-3-540-30140-0_26

View Publication

Locations

Lecture notes in computer science - View

Similar Works

Action	Title	Year	Authors
+	Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings (Extended Abstract)	2004	Josep D ́ iaz María Serna Dimitrios M. Thilikos
+	Efficient algorithms for counting parameterized list H-colorings	2008	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+	Complexity issues on bounded restrictive H-coloring	2007	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+	The Complexity of Restrictive H-Coloring	2002	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+	Counting list h-colorings and variants	2001	Josep Dı́az María Serna Dimitrios Thilikos Touloupas
+	Parameterized Coloring Problems on Threshold Graphs	2019	I. Vinod Reddy
+	Kernels for Below-Upper-Bound Parameterizations of the Hitting Set and Directed Dominating Set Problems	2010	Gregory Gutin Mark Jones Anders Yeo
+	Parameterized Coloring Problems on Threshold Graphs.	2019	I. Vinod Reddy
+	Counting Problems in Parameterized Complexity.	2019	Radu Curticapean
+	Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems	2015	Jiřı́ Fiala Tomáš Gavenčiak Dušan Knop Martin Koutecký Jan Kratochvı́l
+	Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems	2015	Jiřı́ Fiala Tomáš Gavenčiak Dušan Knop Martin Koutecký Jan Kratochvı́l
+	Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)	2021	Dániel Marx Govind S. Sankar Philipp Schepper
+	Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space	2021	Hans L. Bodlaender Carla Groenland Jesper Nederlof Céline M. F. Swennenhuis
+ PDF Chat	Parameterized Problems Complete for Nondeterministic Fpt Time and Logarithmic Space	2023	Hans Leo Bodlaender Carla Groenland Jesper Nederlof Céline M. F. Swennenhuis
+	Fixed-Parameter Tractability of $$(n-k)$$ List Coloring	2019	Aritra Banik Ashwin Jacob Vijay Paliwal Venkatesh Raman
+	Structural Parameterizations of Budgeted Graph Coloring	2021	Susobhan Bandopadhyay Suman Banerjee Aritra Banik Venkatesh Raman
+ PDF Chat	Parameterized Pre-Coloring Extension and List Coloring Problems	2021	Gregory Gutin Diptapriyo Majumdar Sebastian Ordyniak Magnus Wahlström
+	Parameterized Pre-coloring Extension and List Coloring Problems	2019	Gregory Gutin Diptapriyo Majumdar Sebastian Ordyniak Magnus Wahlström
+	Parameterized Pre-coloring Extension and List Coloring Problems	2019	Gregory Gutin Diptapriyo Majumdar Sebastian Ordyniak Magnus Wahlström
+ PDF Chat	Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems	2017	Lars Jaffke Bart M. P. Jansen

Works That Cite This (3)

Action	Title	Year	Authors
+	Complexity issues on bounded restrictive H-coloring	2007	Josep Dı́az Marı́a Serna Dimitrios M. Thilikos
+	Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism	2015	Eun-Jung Kim Christophe Paul Ignasi Sau 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

Works Cited by This (6)

Action	Title	Year	Authors
+	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