Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)
Vadim Lozin, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Mark Siggers, Siani Smith, and Erik Jan van Leeuwen. Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 47:1-47:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lozin_et_al:LIPIcs.ISAAC.2024.47, author = {Lozin, Vadim and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Siggers, Mark and Smith, Siani and van Leeuwen, Erik Jan}, title = {{Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs}}, booktitle = {35th International Symposium on Algorithms and Computation (ISAAC 2024)}, pages = {47:1--47:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-354-6}, ISSN = {1868-8969}, year = {2024}, volume = {322}, editor = {Mestre, Juli\'{a}n and Wirth, Anthony}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.47}, URN = {urn:nbn:de:0030-drops-221747}, doi = {10.4230/LIPIcs.ISAAC.2024.47}, annote = {Keywords: forbidden subgraph, complexity dichotomy, edge subdivision, treewidth} }
Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)
Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{johnson_et_al:LIPIcs.SWAT.2024.29, author = {Johnson, Matthew and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Smith, Siani and van Leeuwen, Erik Jan}, title = {{Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {29:1--29:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.29}, URN = {urn:nbn:de:0030-drops-200699}, doi = {10.4230/LIPIcs.SWAT.2024.29}, annote = {Keywords: multiway cut, planar subcubic graph, complexity dichotomy, graph containment} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Carl Feghali, Felicia Lucke, Daniël Paulusma, and Bernard Ries. Matching Cuts in Graphs of High Girth and H-Free Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{feghali_et_al:LIPIcs.ISAAC.2023.31, author = {Feghali, Carl and Lucke, Felicia and Paulusma, Dani\"{e}l and Ries, Bernard}, title = {{Matching Cuts in Graphs of High Girth and H-Free Graphs}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {31:1--31:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.31}, URN = {urn:nbn:de:0030-drops-193332}, doi = {10.4230/LIPIcs.ISAAC.2023.31}, annote = {Keywords: matching cut, perfect matching, girth, H-free graph} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{johnson_et_al:LIPIcs.MFCS.2023.57, author = {Johnson, Matthew and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Smith, Siani and van Leeuwen, Erik Jan}, title = {{Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {57:1--57:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.57}, URN = {urn:nbn:de:0030-drops-185914}, doi = {10.4230/LIPIcs.MFCS.2023.57}, annote = {Keywords: forbidden subgraphs, independent feedback vertex set, treewidth} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Felicia Lucke, Daniël Paulusma, and Bernard Ries. Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 64:1-64:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lucke_et_al:LIPIcs.MFCS.2023.64, author = {Lucke, Felicia and Paulusma, Dani\"{e}l and Ries, Bernard}, title = {{Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {64:1--64:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.64}, URN = {urn:nbn:de:0030-drops-185981}, doi = {10.4230/LIPIcs.MFCS.2023.64}, annote = {Keywords: matching cut, perfect matching, H-free graph, diameter, radius, dichotomy} }
Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)
Maria Chudnovsky, Neeldhara Misra, Daniel Paulusma, Oliver Schaudt, and Akanksha Agrawal. Vertex Partitioning in Graphs: From Structure to Algorithms (Dagstuhl Seminar 22481). In Dagstuhl Reports, Volume 12, Issue 11, pp. 109-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Article{chudnovsky_et_al:DagRep.12.11.109, author = {Chudnovsky, Maria and Misra, Neeldhara and Paulusma, Daniel and Schaudt, Oliver and Agrawal, Akanksha}, title = {{Vertex Partitioning in Graphs: From Structure to Algorithms (Dagstuhl Seminar 22481)}}, pages = {109--123}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {12}, number = {11}, editor = {Chudnovsky, Maria and Misra, Neeldhara and Paulusma, Daniel and Schaudt, Oliver and Agrawal, Akanksha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.11.109}, URN = {urn:nbn:de:0030-drops-178384}, doi = {10.4230/DagRep.12.11.109}, annote = {Keywords: computational complexity, hereditary graph classes, parameterized algorithms, polynomial-time algorithms, vertex partitioning} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Felicia Lucke, Daniël Paulusma, and Bernard Ries. Finding Matching Cuts in H-Free Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lucke_et_al:LIPIcs.ISAAC.2022.22, author = {Lucke, Felicia and Paulusma, Dani\"{e}l and Ries, Bernard}, title = {{Finding Matching Cuts in H-Free Graphs}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {22:1--22:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.22}, URN = {urn:nbn:de:0030-drops-173076}, doi = {10.4230/LIPIcs.ISAAC.2022.22}, annote = {Keywords: matching cut, perfect matching, H-free graph, computational complexity} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Christoph Brause, Petr Golovach, Barnaby Martin, Daniël Paulusma, and Siani Smith. Partitioning H-Free Graphs of Bounded Diameter. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{brause_et_al:LIPIcs.ISAAC.2021.21, author = {Brause, Christoph and Golovach, Petr and Martin, Barnaby and Paulusma, Dani\"{e}l and Smith, Siani}, title = {{Partitioning H-Free Graphs of Bounded Diameter}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {21:1--21:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.21}, URN = {urn:nbn:de:0030-drops-154543}, doi = {10.4230/LIPIcs.ISAAC.2021.21}, annote = {Keywords: vertex partitioning problem, H-free, diameter, complexity dichotomy} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Benoît Larose, Petar Marković, Barnaby Martin, Daniël Paulusma, Siani Smith, and Stanislav Živný. QCSP on Reflexive Tournaments. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{larose_et_al:LIPIcs.ESA.2021.58, author = {Larose, Beno\^{i}t and Markovi\'{c}, Petar and Martin, Barnaby and Paulusma, Dani\"{e}l and Smith, Siani and \v{Z}ivn\'{y}, Stanislav}, title = {{QCSP on Reflexive Tournaments}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {58:1--58:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.58}, URN = {urn:nbn:de:0030-drops-146392}, doi = {10.4230/LIPIcs.ESA.2021.58}, annote = {Keywords: computational complexity, algorithmic graph theory, quantified constraints, universal algebra, constraint satisfaction} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Giacomo Paesani, Daniël Paulusma, and Paweł Rzążewski. Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 82:1-82:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{paesani_et_al:LIPIcs.MFCS.2021.82, author = {Paesani, Giacomo and Paulusma, Dani\"{e}l and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {82:1--82:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.82}, URN = {urn:nbn:de:0030-drops-145224}, doi = {10.4230/LIPIcs.MFCS.2021.82}, annote = {Keywords: Feedback vertex set, even cycle transversal, odd cactus, forest, block} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Nick Brettell, Jake Horsfield, Andrea Munaro, Giacomo Paesani, and Daniël Paulusma. Bounding the Mim-Width of Hereditary Graph Classes. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{brettell_et_al:LIPIcs.IPEC.2020.6, author = {Brettell, Nick and Horsfield, Jake and Munaro, Andrea and Paesani, Giacomo and Paulusma, Dani\"{e}l}, title = {{Bounding the Mim-Width of Hereditary Graph Classes}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {6:1--6:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.6}, URN = {urn:nbn:de:0030-drops-133099}, doi = {10.4230/LIPIcs.IPEC.2020.6}, annote = {Keywords: Width parameter, mim-width, clique-width, hereditary graph class} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Walter Kern and Daniël Paulusma. Contracting to a Longest Path in H-Free Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kern_et_al:LIPIcs.ISAAC.2020.22, author = {Kern, Walter and Paulusma, Dani\"{e}l}, title = {{Contracting to a Longest Path in H-Free Graphs}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {22:1--22:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.22}, URN = {urn:nbn:de:0030-drops-133664}, doi = {10.4230/LIPIcs.ISAAC.2020.22}, annote = {Keywords: dichotomy, edge contraction, path, cycle, H-free graph} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Jan Bok, Nikola Jedlic̆ková, Barnaby Martin, Daniël Paulusma, and Siani Smith. Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bok_et_al:LIPIcs.ESA.2020.22, author = {Bok, Jan and Jedlic̆kov\'{a}, Nikola and Martin, Barnaby and Paulusma, Dani\"{e}l and Smith, Siani}, title = {{Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {22:1--22:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.22}, URN = {urn:nbn:de:0030-drops-128885}, doi = {10.4230/LIPIcs.ESA.2020.22}, annote = {Keywords: acyclic colouring, star colouring, injective colouring, H-free, dichotomy} }
Published in: Dagstuhl Reports, Volume 9, Issue 6 (2020)
Maria Chudnovsky, Daniel Paulusma, and Oliver Schaudt. Graph Colouring: from Structure to Algorithms (Dagstuhl Seminar 19271). In Dagstuhl Reports, Volume 9, Issue 6, pp. 125-142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{chudnovsky_et_al:DagRep.9.6.125, author = {Chudnovsky, Maria and Paulusma, Daniel and Schaudt, Oliver}, title = {{Graph Colouring: from Structure to Algorithms (Dagstuhl Seminar 19271)}}, pages = {125--142}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {6}, editor = {Chudnovsky, Maria and Paulusma, Daniel and Schaudt, Oliver}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.6.125}, URN = {urn:nbn:de:0030-drops-114905}, doi = {10.4230/DagRep.9.6.125}, annote = {Keywords: (certifying / parameterized / polynomial-time) algorithms, computational complexity, graph colouring, hereditary graph classes} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Barnaby Martin, Daniël Paulusma, and Siani Smith. Colouring H-Free Graphs of Bounded Diameter. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{martin_et_al:LIPIcs.MFCS.2019.14, author = {Martin, Barnaby and Paulusma, Dani\"{e}l and Smith, Siani}, title = {{Colouring H-Free Graphs of Bounded Diameter}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {14:1--14:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.14}, URN = {urn:nbn:de:0030-drops-109584}, doi = {10.4230/LIPIcs.MFCS.2019.14}, annote = {Keywords: vertex colouring, H-free graph, diameter} }
Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, and Stéphane Vialette. Finding a Small Number of Colourful Components. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bulteau_et_al:LIPIcs.CPM.2019.20, author = {Bulteau, Laurent and Dabrowski, Konrad K. and Fertin, Guillaume and Johnson, Matthew and Paulusma, Dani\"{e}l and Vialette, St\'{e}phane}, title = {{Finding a Small Number of Colourful Components}}, booktitle = {30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)}, pages = {20:1--20:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-103-0}, ISSN = {1868-8969}, year = {2019}, volume = {128}, editor = {Pisanti, Nadia and P. Pissis, Solon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.20}, URN = {urn:nbn:de:0030-drops-104914}, doi = {10.4230/LIPIcs.CPM.2019.20}, annote = {Keywords: Colourful component, colourful partition, tree, treewidth, vertex cover} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Tereza Klimosová, Josef Malík, Tomás Masarík, Jana Novotná, Daniël Paulusma, and Veronika Slívová. Colouring (P_r+P_s)-Free Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{klimosova_et_al:LIPIcs.ISAAC.2018.5, author = {Klimosov\'{a}, Tereza and Mal{\'\i}k, Josef and Masar{\'\i}k, Tom\'{a}s and Novotn\'{a}, Jana and Paulusma, Dani\"{e}l and Sl{\'\i}vov\'{a}, Veronika}, title = {{Colouring (P\underliner+P\underlines)-Free Graphs}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {5:1--5:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.5}, URN = {urn:nbn:de:0030-drops-99533}, doi = {10.4230/LIPIcs.ISAAC.2018.5}, annote = {Keywords: vertex colouring, H-free graph, linear forest} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, and Viktor Zamaraev. On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{dabrowski_et_al:LIPIcs.MFCS.2018.63, author = {Dabrowski, Konrad K. and Johnson, Matthew and Paesani, Giacomo and Paulusma, Dani\"{e}l and Zamaraev, Viktor}, title = {{On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {63:1--63:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.63}, URN = {urn:nbn:de:0030-drops-96452}, doi = {10.4230/LIPIcs.MFCS.2018.63}, annote = {Keywords: vertex cover, feedback vertex set, odd cycle transversal, price of independence} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Barnaby Martin, Daniël Paulusma, and Erik Jan van Leeuwen. Disconnected Cuts in Claw-free Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{martin_et_al:LIPIcs.ESA.2018.61, author = {Martin, Barnaby and Paulusma, Dani\"{e}l and van Leeuwen, Erik Jan}, title = {{Disconnected Cuts in Claw-free Graphs}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {61:1--61:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.61}, URN = {urn:nbn:de:0030-drops-95249}, doi = {10.4230/LIPIcs.ESA.2018.61}, annote = {Keywords: disconnected cut, surjective homomorphism, biclique cover, claw-freeness} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Serge Gaspers, Shenwei Huang, and Daniel Paulusma. Colouring Square-Free Graphs without Long Induced Paths. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gaspers_et_al:LIPIcs.STACS.2018.35, author = {Gaspers, Serge and Huang, Shenwei and Paulusma, Daniel}, title = {{Colouring Square-Free Graphs without Long Induced Paths}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {35:1--35:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.35}, URN = {urn:nbn:de:0030-drops-84922}, doi = {10.4230/LIPIcs.STACS.2018.35}, annote = {Keywords: graph colouring, hereditary graph class, clique-width, cycle, path} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Benoit Larose, Barnaby Martin, and Daniel Paulusma. Surjective H-Colouring over Reflexive Digraphs. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{larose_et_al:LIPIcs.STACS.2018.49, author = {Larose, Benoit and Martin, Barnaby and Paulusma, Daniel}, title = {{Surjective H-Colouring over Reflexive Digraphs}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {49:1--49:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.49}, URN = {urn:nbn:de:0030-drops-84882}, doi = {10.4230/LIPIcs.STACS.2018.49}, annote = {Keywords: Surjective H-Coloring, Computational Complexity, Algorithmic Graph Theory, Universal Algebra, Constraint Satisfaction} }
Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Independent Feedback Vertex Set for P_5-free Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bonamy_et_al:LIPIcs.ISAAC.2017.16, author = {Bonamy, Marthe and Dabrowski, Konrad K. and Feghali, Carl and Johnson, Matthew and Paulusma, Dani\"{e}l}, title = {{Independent Feedback Vertex Set for P\underline5-free Graphs}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {16:1--16:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.16}, URN = {urn:nbn:de:0030-drops-82308}, doi = {10.4230/LIPIcs.ISAAC.2017.16}, annote = {Keywords: feedback vertex set, odd cycle transversal, independent set, H-free graph} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Recognizing Graphs Close to Bipartite Graphs. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bonamy_et_al:LIPIcs.MFCS.2017.70, author = {Bonamy, Marthe and Dabrowski, Konrad K. and Feghali, Carl and Johnson, Matthew and Paulusma, Dani\"{e}l}, title = {{Recognizing Graphs Close to Bipartite Graphs}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {70:1--70:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.70}, URN = {urn:nbn:de:0030-drops-80740}, doi = {10.4230/LIPIcs.MFCS.2017.70}, annote = {Keywords: degenerate graphs, near-bipartite graphs, reconfiguration graphs} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma, and Viktor Zamaraev. Clique-Width for Graph Classes Closed under Complementation. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{blanche_et_al:LIPIcs.MFCS.2017.73, author = {Blanch\'{e}, Alexandre and Dabrowski, Konrad K. and Johnson, Matthew and Lozin, Vadim V. and Paulusma, Dani\"{e}l and Zamaraev, Viktor}, title = {{Clique-Width for Graph Classes Closed under Complementation}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {73:1--73:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.73}, URN = {urn:nbn:de:0030-drops-80756}, doi = {10.4230/LIPIcs.MFCS.2017.73}, annote = {Keywords: clique-width, self-complementary graph, forbidden induced subgraph} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Paul Bonsma and Daniël Paulusma. Using Contracted Solution Graphs for Solving Reconfiguration Problems. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bonsma_et_al:LIPIcs.MFCS.2016.20, author = {Bonsma, Paul and Paulusma, Dani\"{e}l}, title = {{Using Contracted Solution Graphs for Solving Reconfiguration Problems}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {20:1--20:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.20}, URN = {urn:nbn:de:0030-drops-64351}, doi = {10.4230/LIPIcs.MFCS.2016.20}, annote = {Keywords: reconfiguration, contraction, dynamic programming, graph coloring} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, and Anthony Stewart. A Linear Kernel for Finding Square Roots of Almost Planar Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{golovach_et_al:LIPIcs.SWAT.2016.4, author = {Golovach, Petr A. and Kratsch, Dieter and Paulusma, Dani\"{e}l and Stewart, Anthony}, title = {{A Linear Kernel for Finding Square Roots of Almost Planar Graphs}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {4:1--4:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.4}, URN = {urn:nbn:de:0030-drops-60333}, doi = {10.4230/LIPIcs.SWAT.2016.4}, annote = {Keywords: planar graphs, square roots, linear kernel} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Konrad K. Dabrowski, François Dross, and Daniël Paulusma. Colouring Diamond-free Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{dabrowski_et_al:LIPIcs.SWAT.2016.16, author = {Dabrowski, Konrad K. and Dross, Fran\c{c}ois and Paulusma, Dani\"{e}l}, title = {{Colouring Diamond-free Graphs}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {16:1--16:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.16}, URN = {urn:nbn:de:0030-drops-60380}, doi = {10.4230/LIPIcs.SWAT.2016.16}, annote = {Keywords: colouring, clique-width, diamond-free, graph class, hereditary graph class} }
Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Konrad K. Dabrowski, Petr A. Golovach, Pim van 't Hof, and Daniel Paulusma. Editing to Eulerian Graphs. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 97-108, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{dabrowski_et_al:LIPIcs.FSTTCS.2014.97, author = {Dabrowski, Konrad K. and Golovach, Petr A. and van 't Hof, Pim and Paulusma, Daniel}, title = {{Editing to Eulerian Graphs}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {97--108}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-77-4}, ISSN = {1868-8969}, year = {2014}, volume = {29}, editor = {Raman, Venkatesh and Suresh, S. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.97}, URN = {urn:nbn:de:0030-drops-48356}, doi = {10.4230/LIPIcs.FSTTCS.2014.97}, annote = {Keywords: Eulerian graphs, graph editing, polynomial algorithm} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Daniel Paulusma, Friedrich Slivovsky, and Stefan Szeider. Model Counting for CNF Formulas of Bounded Modular Treewidth. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 55-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{paulusma_et_al:LIPIcs.STACS.2013.55, author = {Paulusma, Daniel and Slivovsky, Friedrich and Szeider, Stefan}, title = {{Model Counting for CNF Formulas of Bounded Modular Treewidth}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {55--66}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.55}, URN = {urn:nbn:de:0030-drops-39226}, doi = {10.4230/LIPIcs.STACS.2013.55}, annote = {Keywords: Satisfiability, Model Counting, Parameterized Complexity} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider. Satisfiability of Acyclic and Almost Acyclic CNF Formulas. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 84-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{ordyniak_et_al:LIPIcs.FSTTCS.2010.84, author = {Ordyniak, Sebastian and Paulusma, Daniel and Szeider, Stefan}, title = {{Satisfiability of Acyclic and Almost Acyclic CNF Formulas}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {84--95}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.84}, URN = {urn:nbn:de:0030-drops-28556}, doi = {10.4230/LIPIcs.FSTTCS.2010.84}, annote = {Keywords: Satisfiability, chordal bipartite graphs, beta-acyclic hypergraphs, backdoor sets, parameterized complexity} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Jiri Fiala, Marcin Kaminski, Bernard Lidický, and Daniël Paulusma. The k-in-a-path Problem for Claw-free Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 371-382, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{fiala_et_al:LIPIcs.STACS.2010.2469, author = {Fiala, Jiri and Kaminski, Marcin and Lidick\'{y}, Bernard and Paulusma, Dani\"{e}l}, title = {{The k-in-a-path Problem for Claw-free Graphs}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {371--382}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2469}, URN = {urn:nbn:de:0030-drops-24692}, doi = {10.4230/LIPIcs.STACS.2010.2469}, annote = {Keywords: Induced path, claw-free graph, polynomial-time algorithm} }
Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)
Vadim Lozin, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Mark Siggers, Siani Smith, and Erik Jan van Leeuwen. Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 47:1-47:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lozin_et_al:LIPIcs.ISAAC.2024.47, author = {Lozin, Vadim and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Siggers, Mark and Smith, Siani and van Leeuwen, Erik Jan}, title = {{Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs}}, booktitle = {35th International Symposium on Algorithms and Computation (ISAAC 2024)}, pages = {47:1--47:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-354-6}, ISSN = {1868-8969}, year = {2024}, volume = {322}, editor = {Mestre, Juli\'{a}n and Wirth, Anthony}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.47}, URN = {urn:nbn:de:0030-drops-221747}, doi = {10.4230/LIPIcs.ISAAC.2024.47}, annote = {Keywords: forbidden subgraph, complexity dichotomy, edge subdivision, treewidth} }
Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)
Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{johnson_et_al:LIPIcs.SWAT.2024.29, author = {Johnson, Matthew and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Smith, Siani and van Leeuwen, Erik Jan}, title = {{Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {29:1--29:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.29}, URN = {urn:nbn:de:0030-drops-200699}, doi = {10.4230/LIPIcs.SWAT.2024.29}, annote = {Keywords: multiway cut, planar subcubic graph, complexity dichotomy, graph containment} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Carl Feghali, Felicia Lucke, Daniël Paulusma, and Bernard Ries. Matching Cuts in Graphs of High Girth and H-Free Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{feghali_et_al:LIPIcs.ISAAC.2023.31, author = {Feghali, Carl and Lucke, Felicia and Paulusma, Dani\"{e}l and Ries, Bernard}, title = {{Matching Cuts in Graphs of High Girth and H-Free Graphs}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {31:1--31:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.31}, URN = {urn:nbn:de:0030-drops-193332}, doi = {10.4230/LIPIcs.ISAAC.2023.31}, annote = {Keywords: matching cut, perfect matching, girth, H-free graph} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{johnson_et_al:LIPIcs.MFCS.2023.57, author = {Johnson, Matthew and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Smith, Siani and van Leeuwen, Erik Jan}, title = {{Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {57:1--57:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.57}, URN = {urn:nbn:de:0030-drops-185914}, doi = {10.4230/LIPIcs.MFCS.2023.57}, annote = {Keywords: forbidden subgraphs, independent feedback vertex set, treewidth} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Felicia Lucke, Daniël Paulusma, and Bernard Ries. Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 64:1-64:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lucke_et_al:LIPIcs.MFCS.2023.64, author = {Lucke, Felicia and Paulusma, Dani\"{e}l and Ries, Bernard}, title = {{Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {64:1--64:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.64}, URN = {urn:nbn:de:0030-drops-185981}, doi = {10.4230/LIPIcs.MFCS.2023.64}, annote = {Keywords: matching cut, perfect matching, H-free graph, diameter, radius, dichotomy} }
Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)
Maria Chudnovsky, Neeldhara Misra, Daniel Paulusma, Oliver Schaudt, and Akanksha Agrawal. Vertex Partitioning in Graphs: From Structure to Algorithms (Dagstuhl Seminar 22481). In Dagstuhl Reports, Volume 12, Issue 11, pp. 109-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Article{chudnovsky_et_al:DagRep.12.11.109, author = {Chudnovsky, Maria and Misra, Neeldhara and Paulusma, Daniel and Schaudt, Oliver and Agrawal, Akanksha}, title = {{Vertex Partitioning in Graphs: From Structure to Algorithms (Dagstuhl Seminar 22481)}}, pages = {109--123}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {12}, number = {11}, editor = {Chudnovsky, Maria and Misra, Neeldhara and Paulusma, Daniel and Schaudt, Oliver and Agrawal, Akanksha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.11.109}, URN = {urn:nbn:de:0030-drops-178384}, doi = {10.4230/DagRep.12.11.109}, annote = {Keywords: computational complexity, hereditary graph classes, parameterized algorithms, polynomial-time algorithms, vertex partitioning} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Felicia Lucke, Daniël Paulusma, and Bernard Ries. Finding Matching Cuts in H-Free Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lucke_et_al:LIPIcs.ISAAC.2022.22, author = {Lucke, Felicia and Paulusma, Dani\"{e}l and Ries, Bernard}, title = {{Finding Matching Cuts in H-Free Graphs}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {22:1--22:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.22}, URN = {urn:nbn:de:0030-drops-173076}, doi = {10.4230/LIPIcs.ISAAC.2022.22}, annote = {Keywords: matching cut, perfect matching, H-free graph, computational complexity} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Christoph Brause, Petr Golovach, Barnaby Martin, Daniël Paulusma, and Siani Smith. Partitioning H-Free Graphs of Bounded Diameter. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{brause_et_al:LIPIcs.ISAAC.2021.21, author = {Brause, Christoph and Golovach, Petr and Martin, Barnaby and Paulusma, Dani\"{e}l and Smith, Siani}, title = {{Partitioning H-Free Graphs of Bounded Diameter}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {21:1--21:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.21}, URN = {urn:nbn:de:0030-drops-154543}, doi = {10.4230/LIPIcs.ISAAC.2021.21}, annote = {Keywords: vertex partitioning problem, H-free, diameter, complexity dichotomy} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Benoît Larose, Petar Marković, Barnaby Martin, Daniël Paulusma, Siani Smith, and Stanislav Živný. QCSP on Reflexive Tournaments. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{larose_et_al:LIPIcs.ESA.2021.58, author = {Larose, Beno\^{i}t and Markovi\'{c}, Petar and Martin, Barnaby and Paulusma, Dani\"{e}l and Smith, Siani and \v{Z}ivn\'{y}, Stanislav}, title = {{QCSP on Reflexive Tournaments}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {58:1--58:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.58}, URN = {urn:nbn:de:0030-drops-146392}, doi = {10.4230/LIPIcs.ESA.2021.58}, annote = {Keywords: computational complexity, algorithmic graph theory, quantified constraints, universal algebra, constraint satisfaction} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Giacomo Paesani, Daniël Paulusma, and Paweł Rzążewski. Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 82:1-82:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{paesani_et_al:LIPIcs.MFCS.2021.82, author = {Paesani, Giacomo and Paulusma, Dani\"{e}l and Rz\k{a}\.{z}ewski, Pawe{\l}}, title = {{Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {82:1--82:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.82}, URN = {urn:nbn:de:0030-drops-145224}, doi = {10.4230/LIPIcs.MFCS.2021.82}, annote = {Keywords: Feedback vertex set, even cycle transversal, odd cactus, forest, block} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Nick Brettell, Jake Horsfield, Andrea Munaro, Giacomo Paesani, and Daniël Paulusma. Bounding the Mim-Width of Hereditary Graph Classes. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{brettell_et_al:LIPIcs.IPEC.2020.6, author = {Brettell, Nick and Horsfield, Jake and Munaro, Andrea and Paesani, Giacomo and Paulusma, Dani\"{e}l}, title = {{Bounding the Mim-Width of Hereditary Graph Classes}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {6:1--6:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.6}, URN = {urn:nbn:de:0030-drops-133099}, doi = {10.4230/LIPIcs.IPEC.2020.6}, annote = {Keywords: Width parameter, mim-width, clique-width, hereditary graph class} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Walter Kern and Daniël Paulusma. Contracting to a Longest Path in H-Free Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kern_et_al:LIPIcs.ISAAC.2020.22, author = {Kern, Walter and Paulusma, Dani\"{e}l}, title = {{Contracting to a Longest Path in H-Free Graphs}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {22:1--22:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.22}, URN = {urn:nbn:de:0030-drops-133664}, doi = {10.4230/LIPIcs.ISAAC.2020.22}, annote = {Keywords: dichotomy, edge contraction, path, cycle, H-free graph} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Jan Bok, Nikola Jedlic̆ková, Barnaby Martin, Daniël Paulusma, and Siani Smith. Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bok_et_al:LIPIcs.ESA.2020.22, author = {Bok, Jan and Jedlic̆kov\'{a}, Nikola and Martin, Barnaby and Paulusma, Dani\"{e}l and Smith, Siani}, title = {{Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {22:1--22:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.22}, URN = {urn:nbn:de:0030-drops-128885}, doi = {10.4230/LIPIcs.ESA.2020.22}, annote = {Keywords: acyclic colouring, star colouring, injective colouring, H-free, dichotomy} }
Published in: Dagstuhl Reports, Volume 9, Issue 6 (2020)
Maria Chudnovsky, Daniel Paulusma, and Oliver Schaudt. Graph Colouring: from Structure to Algorithms (Dagstuhl Seminar 19271). In Dagstuhl Reports, Volume 9, Issue 6, pp. 125-142, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{chudnovsky_et_al:DagRep.9.6.125, author = {Chudnovsky, Maria and Paulusma, Daniel and Schaudt, Oliver}, title = {{Graph Colouring: from Structure to Algorithms (Dagstuhl Seminar 19271)}}, pages = {125--142}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {6}, editor = {Chudnovsky, Maria and Paulusma, Daniel and Schaudt, Oliver}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.6.125}, URN = {urn:nbn:de:0030-drops-114905}, doi = {10.4230/DagRep.9.6.125}, annote = {Keywords: (certifying / parameterized / polynomial-time) algorithms, computational complexity, graph colouring, hereditary graph classes} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Barnaby Martin, Daniël Paulusma, and Siani Smith. Colouring H-Free Graphs of Bounded Diameter. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{martin_et_al:LIPIcs.MFCS.2019.14, author = {Martin, Barnaby and Paulusma, Dani\"{e}l and Smith, Siani}, title = {{Colouring H-Free Graphs of Bounded Diameter}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {14:1--14:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.14}, URN = {urn:nbn:de:0030-drops-109584}, doi = {10.4230/LIPIcs.MFCS.2019.14}, annote = {Keywords: vertex colouring, H-free graph, diameter} }
Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, and Stéphane Vialette. Finding a Small Number of Colourful Components. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bulteau_et_al:LIPIcs.CPM.2019.20, author = {Bulteau, Laurent and Dabrowski, Konrad K. and Fertin, Guillaume and Johnson, Matthew and Paulusma, Dani\"{e}l and Vialette, St\'{e}phane}, title = {{Finding a Small Number of Colourful Components}}, booktitle = {30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)}, pages = {20:1--20:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-103-0}, ISSN = {1868-8969}, year = {2019}, volume = {128}, editor = {Pisanti, Nadia and P. Pissis, Solon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.20}, URN = {urn:nbn:de:0030-drops-104914}, doi = {10.4230/LIPIcs.CPM.2019.20}, annote = {Keywords: Colourful component, colourful partition, tree, treewidth, vertex cover} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Tereza Klimosová, Josef Malík, Tomás Masarík, Jana Novotná, Daniël Paulusma, and Veronika Slívová. Colouring (P_r+P_s)-Free Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{klimosova_et_al:LIPIcs.ISAAC.2018.5, author = {Klimosov\'{a}, Tereza and Mal{\'\i}k, Josef and Masar{\'\i}k, Tom\'{a}s and Novotn\'{a}, Jana and Paulusma, Dani\"{e}l and Sl{\'\i}vov\'{a}, Veronika}, title = {{Colouring (P\underliner+P\underlines)-Free Graphs}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {5:1--5:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.5}, URN = {urn:nbn:de:0030-drops-99533}, doi = {10.4230/LIPIcs.ISAAC.2018.5}, annote = {Keywords: vertex colouring, H-free graph, linear forest} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Konrad K. Dabrowski, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, and Viktor Zamaraev. On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{dabrowski_et_al:LIPIcs.MFCS.2018.63, author = {Dabrowski, Konrad K. and Johnson, Matthew and Paesani, Giacomo and Paulusma, Dani\"{e}l and Zamaraev, Viktor}, title = {{On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {63:1--63:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.63}, URN = {urn:nbn:de:0030-drops-96452}, doi = {10.4230/LIPIcs.MFCS.2018.63}, annote = {Keywords: vertex cover, feedback vertex set, odd cycle transversal, price of independence} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Barnaby Martin, Daniël Paulusma, and Erik Jan van Leeuwen. Disconnected Cuts in Claw-free Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{martin_et_al:LIPIcs.ESA.2018.61, author = {Martin, Barnaby and Paulusma, Dani\"{e}l and van Leeuwen, Erik Jan}, title = {{Disconnected Cuts in Claw-free Graphs}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {61:1--61:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.61}, URN = {urn:nbn:de:0030-drops-95249}, doi = {10.4230/LIPIcs.ESA.2018.61}, annote = {Keywords: disconnected cut, surjective homomorphism, biclique cover, claw-freeness} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Serge Gaspers, Shenwei Huang, and Daniel Paulusma. Colouring Square-Free Graphs without Long Induced Paths. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gaspers_et_al:LIPIcs.STACS.2018.35, author = {Gaspers, Serge and Huang, Shenwei and Paulusma, Daniel}, title = {{Colouring Square-Free Graphs without Long Induced Paths}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {35:1--35:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.35}, URN = {urn:nbn:de:0030-drops-84922}, doi = {10.4230/LIPIcs.STACS.2018.35}, annote = {Keywords: graph colouring, hereditary graph class, clique-width, cycle, path} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Benoit Larose, Barnaby Martin, and Daniel Paulusma. Surjective H-Colouring over Reflexive Digraphs. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{larose_et_al:LIPIcs.STACS.2018.49, author = {Larose, Benoit and Martin, Barnaby and Paulusma, Daniel}, title = {{Surjective H-Colouring over Reflexive Digraphs}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {49:1--49:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.49}, URN = {urn:nbn:de:0030-drops-84882}, doi = {10.4230/LIPIcs.STACS.2018.49}, annote = {Keywords: Surjective H-Coloring, Computational Complexity, Algorithmic Graph Theory, Universal Algebra, Constraint Satisfaction} }
Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Independent Feedback Vertex Set for P_5-free Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bonamy_et_al:LIPIcs.ISAAC.2017.16, author = {Bonamy, Marthe and Dabrowski, Konrad K. and Feghali, Carl and Johnson, Matthew and Paulusma, Dani\"{e}l}, title = {{Independent Feedback Vertex Set for P\underline5-free Graphs}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {16:1--16:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.16}, URN = {urn:nbn:de:0030-drops-82308}, doi = {10.4230/LIPIcs.ISAAC.2017.16}, annote = {Keywords: feedback vertex set, odd cycle transversal, independent set, H-free graph} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Recognizing Graphs Close to Bipartite Graphs. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bonamy_et_al:LIPIcs.MFCS.2017.70, author = {Bonamy, Marthe and Dabrowski, Konrad K. and Feghali, Carl and Johnson, Matthew and Paulusma, Dani\"{e}l}, title = {{Recognizing Graphs Close to Bipartite Graphs}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {70:1--70:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.70}, URN = {urn:nbn:de:0030-drops-80740}, doi = {10.4230/LIPIcs.MFCS.2017.70}, annote = {Keywords: degenerate graphs, near-bipartite graphs, reconfiguration graphs} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma, and Viktor Zamaraev. Clique-Width for Graph Classes Closed under Complementation. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{blanche_et_al:LIPIcs.MFCS.2017.73, author = {Blanch\'{e}, Alexandre and Dabrowski, Konrad K. and Johnson, Matthew and Lozin, Vadim V. and Paulusma, Dani\"{e}l and Zamaraev, Viktor}, title = {{Clique-Width for Graph Classes Closed under Complementation}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {73:1--73:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.73}, URN = {urn:nbn:de:0030-drops-80756}, doi = {10.4230/LIPIcs.MFCS.2017.73}, annote = {Keywords: clique-width, self-complementary graph, forbidden induced subgraph} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Paul Bonsma and Daniël Paulusma. Using Contracted Solution Graphs for Solving Reconfiguration Problems. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bonsma_et_al:LIPIcs.MFCS.2016.20, author = {Bonsma, Paul and Paulusma, Dani\"{e}l}, title = {{Using Contracted Solution Graphs for Solving Reconfiguration Problems}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {20:1--20:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.20}, URN = {urn:nbn:de:0030-drops-64351}, doi = {10.4230/LIPIcs.MFCS.2016.20}, annote = {Keywords: reconfiguration, contraction, dynamic programming, graph coloring} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, and Anthony Stewart. A Linear Kernel for Finding Square Roots of Almost Planar Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{golovach_et_al:LIPIcs.SWAT.2016.4, author = {Golovach, Petr A. and Kratsch, Dieter and Paulusma, Dani\"{e}l and Stewart, Anthony}, title = {{A Linear Kernel for Finding Square Roots of Almost Planar Graphs}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {4:1--4:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.4}, URN = {urn:nbn:de:0030-drops-60333}, doi = {10.4230/LIPIcs.SWAT.2016.4}, annote = {Keywords: planar graphs, square roots, linear kernel} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Konrad K. Dabrowski, François Dross, and Daniël Paulusma. Colouring Diamond-free Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{dabrowski_et_al:LIPIcs.SWAT.2016.16, author = {Dabrowski, Konrad K. and Dross, Fran\c{c}ois and Paulusma, Dani\"{e}l}, title = {{Colouring Diamond-free Graphs}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {16:1--16:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.16}, URN = {urn:nbn:de:0030-drops-60380}, doi = {10.4230/LIPIcs.SWAT.2016.16}, annote = {Keywords: colouring, clique-width, diamond-free, graph class, hereditary graph class} }
Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Konrad K. Dabrowski, Petr A. Golovach, Pim van 't Hof, and Daniel Paulusma. Editing to Eulerian Graphs. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 97-108, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{dabrowski_et_al:LIPIcs.FSTTCS.2014.97, author = {Dabrowski, Konrad K. and Golovach, Petr A. and van 't Hof, Pim and Paulusma, Daniel}, title = {{Editing to Eulerian Graphs}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {97--108}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-77-4}, ISSN = {1868-8969}, year = {2014}, volume = {29}, editor = {Raman, Venkatesh and Suresh, S. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.97}, URN = {urn:nbn:de:0030-drops-48356}, doi = {10.4230/LIPIcs.FSTTCS.2014.97}, annote = {Keywords: Eulerian graphs, graph editing, polynomial algorithm} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Daniel Paulusma, Friedrich Slivovsky, and Stefan Szeider. Model Counting for CNF Formulas of Bounded Modular Treewidth. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 55-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{paulusma_et_al:LIPIcs.STACS.2013.55, author = {Paulusma, Daniel and Slivovsky, Friedrich and Szeider, Stefan}, title = {{Model Counting for CNF Formulas of Bounded Modular Treewidth}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {55--66}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.55}, URN = {urn:nbn:de:0030-drops-39226}, doi = {10.4230/LIPIcs.STACS.2013.55}, annote = {Keywords: Satisfiability, Model Counting, Parameterized Complexity} }
Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Sebastian Ordyniak, Daniel Paulusma, and Stefan Szeider. Satisfiability of Acyclic and Almost Acyclic CNF Formulas. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 84-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{ordyniak_et_al:LIPIcs.FSTTCS.2010.84, author = {Ordyniak, Sebastian and Paulusma, Daniel and Szeider, Stefan}, title = {{Satisfiability of Acyclic and Almost Acyclic CNF Formulas}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {84--95}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.84}, URN = {urn:nbn:de:0030-drops-28556}, doi = {10.4230/LIPIcs.FSTTCS.2010.84}, annote = {Keywords: Satisfiability, chordal bipartite graphs, beta-acyclic hypergraphs, backdoor sets, parameterized complexity} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Jiri Fiala, Marcin Kaminski, Bernard Lidický, and Daniël Paulusma. The k-in-a-path Problem for Claw-free Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 371-382, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{fiala_et_al:LIPIcs.STACS.2010.2469, author = {Fiala, Jiri and Kaminski, Marcin and Lidick\'{y}, Bernard and Paulusma, Dani\"{e}l}, title = {{The k-in-a-path Problem for Claw-free Graphs}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {371--382}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2469}, URN = {urn:nbn:de:0030-drops-24692}, doi = {10.4230/LIPIcs.STACS.2010.2469}, annote = {Keywords: Induced path, claw-free graph, polynomial-time algorithm} }
Feedback for Dagstuhl Publishing