Document Open Access Logo

Grundy Distinguishes Treewidth from Pathwidth

Authors Rémy Belmonte, Eun Jung Kim, Michael Lampis , Valia Mitsou, Yota Otachi

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.14.pdf
  • Filesize: 0.61 MB
  • 19 pages

Document Identifiers

Author Details

Rémy Belmonte
  • University of Electro-Communications, Chofu, Tokyo, Japan
Eun Jung Kim
  • Université Paris-Dauphine, PSL University, CNRS, LAMSADE, Paris, France
Michael Lampis
  • Université Paris-Dauphine, PSL University, CNRS, LAMSADE, Paris, France
Valia Mitsou
  • Université de Paris, IRIF, CNRS, France
Yota Otachi
  • Nagoya University, Nagoya, 464-8601, Japan

Funding

Supported under the PRC CNRS JSPS 2019-2020 program, project PARAGA (Parameterized Approximation Graph Algorithms).
  • Belmonte, Rémy: The author was partially supported by JSPS KAKENHI Grant Number JP18K11157.
  • Kim, Eun Jung: The author was partially supported by ANR JCJC Grant Number 18-CE40-0025-01
  • Otachi, Yota: The author was partially supported by JSPS KAKENHI Grant Numbers JP18K11168, JP18K11169, JP18H04091.

Cite AsGet BibTex

Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi. Grundy Distinguishes Treewidth from Pathwidth. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ESA.2020.14

Abstract

Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the "price of generality" of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status deteriorate from fixed-parameter tractable to intractable? This type of question is by now very well-studied, but, somewhat strikingly, the algorithmic frontier between the two (arguably) most central width notions, treewidth and pathwidth, is still not understood: currently, no natural graph problem is known to be W-hard for one but FPT for the other. Indeed, a surprising development of the last few years has been the observation that for many of the most paradigmatic problems, their complexities for the two parameters actually coincide exactly, despite the fact that treewidth is a much more general parameter. It would thus appear that the extra generality of treewidth over pathwidth often comes "for free". Our main contribution in this paper is to uncover the first natural example where this generality comes with a high price. We consider Grundy Coloring, a variation of coloring where one seeks to calculate the worst possible coloring that could be assigned to a graph by a greedy First-Fit algorithm. We show that this well-studied problem is FPT parameterized by pathwidth; however, it becomes significantly harder (W[1]-hard) when parameterized by treewidth. Furthermore, we show that Grundy Coloring makes a second complexity jump for more general widths, as it becomes para-NP-hard for clique-width. Hence, Grundy Coloring nicely captures the complexity trade-offs between the three most well-studied parameters. Completing the picture, we show that Grundy Coloring is FPT parameterized by modular-width.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Treewidth
  • Pathwidth
  • Clique-width
  • Grundy Coloring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Pierre Aboulker, Édouard Bonnet, Eun Jung Kim, and Florian Sikora. Grundy coloring & friends, half-graphs, bicliques. In 37th Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2020. Google Scholar
  2. Eric Angel, Evripidis Bampis, Bruno Escoffier, and Michael Lampis. Parameterized power vertex cover. Discrete Mathematics & Theoretical Computer Science, 20(2), 2018. URL: http://dmtcs.episciences.org/4873.
  3. Júlio Araújo and Cláudia Linhares Sales. On the grundy number of graphs with few p_4’s. Discrete Applied Mathematics, 160(18):2514-2522, 2012. URL: https://doi.org/10.1016/j.dam.2011.08.016.
  4. Ashwin Arulselvan, Ágnes Cseh, Martin Groß, David F. Manlove, and Jannik Matuschke. Matchings with lower quotas: Algorithms and complexity. Algorithmica, 80(1):185-208, 2018. URL: https://doi.org/10.1007/s00453-016-0252-6.
  5. Haris Aziz, Serge Gaspers, Edward J. Lee, and Kamran Najeebullah. Defender stackelberg game with inverse geodesic length as utility metric. In Elisabeth André, Sven Koenig, Mehdi Dastani, and Gita Sukthankar, editors, Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pages 694-702. International Foundation for Autonomous Agents and Multiagent Systems Richland, SC, USA / ACM, 2018. URL: http://dl.acm.org/citation.cfm?id=3237486.
  6. Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, and Michael Lampis. New results on directed edge dominating set. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPIcs, pages 67:1-67:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.67.
  7. Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, and Yota Otachi. Parameterized complexity of safe set. In Pinar Heggernes, editor, Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings, volume 11485 of Lecture Notes in Computer Science, pages 38-49. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-17402-6_4.
  8. Rémy Belmonte, Michael Lampis, and Valia Mitsou. Parameterized (approximate) defective coloring. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages 10:1-10:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.10.
  9. Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, and Ilan Newman. Treewidth governs the complexity of target set selection. Discrete Optimization, 8(1):87-96, 2011. URL: https://doi.org/10.1016/j.disopt.2010.09.007.
  10. Matthias Bentert, Klaus Heeger, and Dušan Knop. Length-bounded cuts: Proper interval graphs and structural parameters, 2019. URL: http://arxiv.org/abs/1910.03409.
  11. Nadja Betzler, Robert Bredereck, Rolf Niedermeier, and Johannes Uhlmann. On bounded-degree vertex deletion parameterized by treewidth. Discrete Applied Mathematics, 160(1-2):53-60, 2012. URL: https://doi.org/10.1016/j.dam.2011.08.013.
  12. Marzio De Biasi and Juho Lauri. On the complexity of restoring corrupted colorings. J. Comb. Optim., 37(4):1150-1169, 2019. URL: https://doi.org/10.1007/s10878-018-0342-2.
  13. Édouard Bonnet, Florent Foucaud, Eun Jung Kim, and Florian Sikora. Complexity of grundy coloring and its variants. Discrete Applied Mathematics, 243:99-114, 2018. URL: https://doi.org/10.1016/j.dam.2017.12.022.
  14. Édouard Bonnet, Michael Lampis, and Vangelis Th. Paschos. Time-approximation trade-offs for inapproximable problems. J. Comput. Syst. Sci., 92:171-180, 2018. URL: https://doi.org/10.1016/j.jcss.2017.09.009.
  15. Édouard Bonnet and Nidhi Purohit. Metric dimension parameterized by treewidth. CoRR, abs/1907.08093, 2019. URL: http://arxiv.org/abs/1907.08093.
  16. Hajo Broersma, Petr A. Golovach, and Viresh Patel. Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. Theor. Comput. Sci., 485:69-84, 2013. URL: https://doi.org/10.1016/j.tcs.2013.03.008.
  17. Claude A. Christen and Stanley M. Selkow. Some perfect coloring properties of graphs. J. Comb. Theory, Ser. B, 27(1):49-59, 1979. URL: https://doi.org/10.1016/0095-8956(79)90067-4.
  18. Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  19. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125-150, 2000. URL: https://doi.org/10.1007/s002249910009.
  20. Radu Curticapean and Dániel Marx. Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1650-1669. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch113.
  21. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  22. Guilherme de C. M. Gomes, Carlos V. G. C. Lima, and Vinícius Fernandes dos Santos. Parameterized complexity of equitable coloring. Discrete Mathematics & Theoretical Computer Science, 21(1), 2019. URL: http://dmtcs.episciences.org/5464.
  23. Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke. Complexity and approximability of parameterized max-csps. Algorithmica, 79(1):230-250, 2017. URL: https://doi.org/10.1007/s00453-017-0310-8.
  24. Michael Dom, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger. Capacitated domination and covering: A parameterized perspective. In Martin Grohe and Rolf Niedermeier, editors, Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings, volume 5018 of Lecture Notes in Computer Science, pages 78-90. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-79723-4_9.
  25. Pavel Dvorák and Dusan Knop. Parameterized complexity of length-bounded cuts and multicuts. Algorithmica, 80(12):3597-3617, 2018. URL: https://doi.org/10.1007/s00453-018-0408-7.
  26. Eduard Eiben, Robert Ganian, K. Kangas, and Sebastian Ordyniak. Counting linear extensions: Parameterizations by treewidth. Algorithmica, 81(4):1657-1683, 2019. URL: https://doi.org/10.1007/s00453-018-0496-4.
  27. Eduard Eiben, Robert Ganian, and Sebastian Ordyniak. A structural approach to activity selection. In Jérôme Lang, editor, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden., pages 203-209. ijcai.org, 2018. URL: https://doi.org/10.24963/ijcai.2018/28.
  28. Rosa Enciso, Michael R. Fellows, Jiong Guo, Iyad A. Kanj, Frances A. Rosamond, and Ondrej Suchý. What makes equitable connected partition easy. In Jianer Chen and Fedor V. Fomin, editors, Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers, volume 5917 of Lecture Notes in Computer Science, pages 122-133. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-11269-0_10.
  29. Alina Ene, Matthias Mnich, Marcin Pilipczuk, and Andrej Risteski. On routing disjoint paths in bounded treewidth graphs. In SWAT, volume 53 of LIPIcs, pages 15:1-15:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  30. Paul Erdös, Stephen T. Hedetniemi, Renu C. Laskar, and Geert C. E. Prins. On the equality of the partial grundy and upper ochromatic numbers of graphs. Discrete Mathematics, 272(1):53-64, 2003. URL: https://doi.org/10.1016/S0012-365X(03)00184-5.
  31. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, Stefan Szeider, and Carsten Thomassen. On the complexity of some colorful problems parameterized by treewidth. Inf. Comput., 209(2):143-153, 2011. URL: https://doi.org/10.1016/j.ic.2010.11.026.
  32. Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci., 410(1):53-61, 2009. Google Scholar
  33. Jirí Fiala, Petr A. Golovach, and Jan Kratochvíl. Parameterized complexity of coloring problems: Treewidth versus vertex cover. Theor. Comput. Sci., 412(23):2513-2523, 2011. URL: https://doi.org/10.1016/j.tcs.2010.10.043.
  34. Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase. New algorithms for maximum disjoint paths based on tree-likeness. In ESA, volume 57 of LIPIcs, pages 42:1-42:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  35. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Algorithmic lower bounds for problems parameterized with clique-width. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 493-502. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.42.
  36. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput., 43(5):1541-1563, 2014. URL: https://doi.org/10.1137/130910932.
  37. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Clique-width III: hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algorithms, 15(1):9:1-9:27, 2019. URL: https://doi.org/10.1145/3280824.
  38. Jakub Gajarský, Michael Lampis, and Sebastian Ordyniak. Parameterized algorithms for modular-width. In Gregory Z. Gutin and Stefan Szeider, editors, Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, volume 8246 of Lecture Notes in Computer Science, pages 163-176. Springer, 2013. URL: https://doi.org/10.1007/978-3-319-03898-8_15.
  39. Robert Ganian, Fabian Klute, and Sebastian Ordyniak. On structural parameterizations of the bounded-degree vertex deletion problem. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, volume 96 of LIPIcs, pages 33:1-33:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.33.
  40. Robert Ganian and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP. Artif. Intell., 257:61-71, 2018. URL: https://doi.org/10.1016/j.artint.2017.12.006.
  41. Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3-20, 1997. URL: https://doi.org/10.1007/BF02523685.
  42. Elisabeth Gassner. The steiner forest problem revisited. J. Discrete Algorithms, 8(2):154-163, 2010. URL: https://doi.org/10.1016/j.jda.2009.05.002.
  43. Gregory Z. Gutin, Mark Jones, and Magnus Wahlström. The mixed chinese postman problem parameterized by pathwidth and treedepth. SIAM J. Discrete Math., 30(4):2177-2205, 2016. URL: https://doi.org/10.1137/15M1034337.
  44. András Gyárfás and Jenö Lehel. On-line and first fit colorings of graphs. Journal of Graph Theory, 12(2):217-227, 1988. URL: https://doi.org/10.1002/jgt.3190120212.
  45. Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, and Florian Sikora. Parameterized orientable deletion. In David Eppstein, editor, 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018, June 18-20, 2018, Malmö, Sweden, volume 101 of LIPIcs, pages 24:1-24:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.SWAT.2018.24.
  46. Frédéric Havet and Leonardo Sampaio. On the grundy and b-chromatic numbers of a graph. Algorithmica, 65(4):885-899, 2013. URL: https://doi.org/10.1007/s00453-011-9604-4.
  47. Ramin Javadi and Amir Nikabadi. On the parameterized complexity of sparsest cut and small-set expansion problems, 2019. URL: http://arxiv.org/abs/1910.12353.
  48. Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structurally parameterized d-scattered set. In Andreas Brandstädt, Ekkehard Köhler, and Klaus Meer, editors, Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, volume 11159 of Lecture Notes in Computer Science, pages 292-305. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-00256-5_24.
  49. Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structural parameters, tight bounds, and approximation for (k, r)-center. Discrete Applied Mathematics, 264:90-117, 2019. URL: https://doi.org/10.1016/j.dam.2018.11.002.
  50. Chamanvir Kaur and Neeldhara Misra. On the parameterized complexity of spanning trees with small vertex covers. In CALDAM, volume 12016 of Lecture Notes in Computer Science, pages 427-438. Springer, 2020. Google Scholar
  51. Leon Kellerhals and Tomohiro Koana. Parameterized complexity of geodetic set, 2020. URL: http://arxiv.org/abs/2001.03098.
  52. Hal A. Kierstead and Karin Rebecca Saoub. First-fit coloring of bounded tolerance graphs. Discrete Applied Mathematics, 159(7):605-611, 2011. URL: https://doi.org/10.1016/j.dam.2010.05.002.
  53. Hal A. Kierstead, David A. Smith, and William T. Trotter. First-fit coloring on interval graphs has performance ratio at least 5. Eur. J. Comb., 51:236-254, 2016. URL: https://doi.org/10.1016/j.ejc.2015.05.015.
  54. Dusan Knop, Tomás Masarík, and Tomás Toufar. Parameterized complexity of fair vertex evaluation problems. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany., volume 138 of LIPIcs, pages 33:1-33:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.33.
  55. Guy Kortsarz. A lower bound for approximating grundy numbering. Discrete Mathematics & Theoretical Computer Science, 9(1), 2007. URL: http://dmtcs.episciences.org/391.
  56. Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica, 64(1):19-37, 2012. URL: https://doi.org/10.1007/s00453-011-9554-x.
  57. Michael Lampis. Parameterized maximum path coloring. Theor. Comput. Sci., 511:42-53, 2013. URL: https://doi.org/10.1016/j.tcs.2013.01.012.
  58. Michael Lampis. Model checking lower bounds for simple graphs. Logical Methods in Computer Science, 10(1), 2014. URL: https://doi.org/10.2168/LMCS-10(1:18)2014.
  59. Michael Lampis and Valia Mitsou. Treewidth with a quantifier alternation revisited. In Daniel Lokshtanov and Naomi Nishimura, editors, 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 6-8, 2017, Vienna, Austria, volume 89 of LIPIcs, pages 26:1-26:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.IPEC.2017.26.
  60. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms, 14(2):13:1-13:30, 2018. URL: https://doi.org/10.1145/3170442.
  61. Dániel Marx and Michal Pilipczuk. Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask). In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, volume 25 of LIPIcs, pages 542-553. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. URL: https://doi.org/10.4230/LIPIcs.STACS.2014.542.
  62. Kitty Meeks and Alexander Scott. The parameterised complexity of list problems on graphs of bounded treewidth. Inf. Comput., 251:91-103, 2016. URL: https://doi.org/10.1016/j.ic.2016.08.001.
  63. Kitty Meeks and Fiona Skerman. The parameterised complexity of computing the maximum modularity of a graph. In IPEC, volume 115 of LIPIcs, pages 9:1-9:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  64. Burkhard Monien. The bandwidth minimization problem for caterpillars with hair length 3 is np-complete. SIAM Journal on Algebraic Discrete Methods, 7(4):505-512, 1986. Google Scholar
  65. N. S. Narayanaswamy and R. Subhash Babu. A note on first-fit coloring of interval graphs. Order, 25(1):49-53, 2008. URL: https://doi.org/10.1007/s11083-008-9076-6.
  66. Jaroslav Nesetril and Patrice Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb., 27(6):1022-1041, 2006. URL: https://doi.org/10.1016/j.ejc.2005.01.010.
  67. André Nichterlein, Rolf Niedermeier, Johannes Uhlmann, and Mathias Weller. On tractable cases of target set selection. Social Netw. Analys. Mining, 3(2):233-256, 2013. URL: https://doi.org/10.1007/s13278-012-0067-7.
  68. Sebastian Ordyniak, Daniël Paulusma, and Stefan Szeider. Satisfiability of acyclic and almost acyclic CNF formulas. Theor. Comput. Sci., 481:85-99, 2013. URL: https://doi.org/10.1016/j.tcs.2012.12.039.
  69. Igor Razgon. On obdds for cnfs of bounded treewidth. In Chitta Baral, Giuseppe De Giacomo, and Thomas Eiter, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20-24, 2014. AAAI Press, 2014. URL: http://www.aaai.org/ocs/index.php/KR/KR14/paper/view/7982.
  70. Marko Samer and Stefan Szeider. Constraint satisfaction with bounded treewidth revisited. J. Comput. Syst. Sci., 76(2):103-114, 2010. URL: https://doi.org/10.1016/j.jcss.2009.04.003.
  71. Marko Samer and Stefan Szeider. Tractable cases of the extended global cardinality constraint. Constraints, 16(1):1-24, 2011. URL: https://doi.org/10.1007/s10601-009-9079-y.
  72. Stefan Szeider. Not so easy problems for tree decomposable graphs. CoRR, abs/1107.1177, 2011. URL: http://arxiv.org/abs/1107.1177.
  73. Zixing Tang, Baoyindureng Wu, Lin Hu, and Manouchehr Zaker. More bounds for the grundy number of graphs. J. Comb. Optim., 33(2):580-589, 2017. URL: https://doi.org/10.1007/s10878-015-9981-8.
  74. Jan Arne Telle and Andrzej Proskurowski. Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math., 10(4):529-550, 1997. URL: https://doi.org/10.1137/S0895480194275825.
  75. Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 566-577. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-04128-0_51.
  76. Manouchehr Zaker. Grundy chromatic number of the complement of bipartite graphs. Australasian J. Combinatorics, 31:325-330, 2005. URL: http://ajc.maths.uq.edu.au/pdf/31/ajc_v31_p325.pdf.
  77. Manouchehr Zaker. Results on the grundy chromatic number of graphs. Discrete Mathematics, 306(23):3166-3173, 2006. URL: https://doi.org/10.1016/j.disc.2005.06.044.
  78. Manouchehr Zaker. Inequalities for the grundy chromatic number of graphs. Discrete Applied Mathematics, 155(18):2567-2572, 2007. URL: https://doi.org/10.1016/j.dam.2007.07.002.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact