Accepted Papers

WG 2019 Accepted Papers


 The abstracts of the accepted papers can be accessed here


  1. Karolina Okrasa and Paweł Rzążewski. Subexponential algorithms for variants of homomorphism problem in string graphs
  2. Guillaume Ducoffe. The 4-Steiner Root Problem
  3. Bart Jansen, László Kozma and Jesper Nederlof. Hamiltonicity below Dirac’s condition
  4. Ararat Harutyunyan, Michael Lampis, Vadim Lozin and Jerome Monnot. Maximum Independent Sets in Subcubic Graphs: New Results
  5. Sebastian Wiederrecht, Meike Hatzel and Roman Rabinovich. Cyclewidth and the Grid Theorem for Perfect Matching Width of Bipartite Graphs
  6. Étienne Bamas and Louis Esperet. Local approximation of the Maximum Cut in regular graphs
  7. Pierre Bergé, Benjamin Mouscadet, Arpad Rimmel and Joanna Tomasik. Fixed-parameter tractability of counting small minimum (S,T)-cuts
  8. Torben Hagerup. Fast Breadth-First Search in Still Less Space
  9. Huib Donkers and Bart M.P. Jansen. A Turing Kernelization Dichotomy for Structural Parameterizations of F-Minor-Free Deletion
  10. Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner and Birgit Vogtenhuber. Flip distances between graph orientations
  11. Bogdan Alecu, Aistis Atminas and Vadim Lozin. Graph functionality
  12. Ivan Bliznets and Danil Sagunov. On Happy Colorings, Cuts, and Structural Parameterizations
  13. Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito and Moritz Muehlenthaler. Shortest Reconfiguration of Matchings
  14. Yann Disser, Andreas Emil Feldmann, Max Klimm and Jochen Koenemann. Travelling on Graphs with Small Highway Dimension
  15. Robert Ganian and Sebastian Ordyniak. The Power of Cut-Based Parameters for Computing Edge Disjoint Paths
  16. Patrizio Angelini, Michael Bekos, Martin Gronemann and Antonios Symvonis. Geometric Representations of Dichotomous Ordinal Data
  17. Svein Høgemo, Jan Arne Telle and Erlend Raa Vågset. Linear MIM-width of Trees
  18. Dibyayan Chakraborty, Joydeep Mukherjee and Sandip Das. Approximating Minimum Dominating Set on String graphs
  19. Meghana Nasre, Prajakta Nimbhorkar and Nada Pulath. Classified Rank-Maximal Matchings and Popular Matchings -- Algorithms and Hardness
  20. Therese Biedl, Ahmad Biniaz, Veronika Irvine, Kshitij Jain, Philipp Kindermann and Anna Lubiw. Maximum Matchings and Minimum Blocking Sets in Theta-6 Graphs
  21. Edin Husic and Martin Milanič. A polynomial-time algorithm for the independent set problem in P10,C4,C6-free graphs
  22. Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono and Yota Otachi. Independent Set Reconfiguration Parameterized by Modular-Width
  23. Martin Dyer, Catherine Greenhill and Haiko Muller. Counting independent sets in graphs with bounded bipartite pathwidth
  24. Steven Chaplick. Intersection Graphs of Non-Crossing Paths
  25. Rahnuma Islam Nishat and Sue Whitesides. Reconfiguring Hamiltonian Cycles in L-Shaped Grid Graphs
  26. Jan Böker. Color Refinement, Homomorphisms, and Hypergraphs
  27. Daniel Gonçalves. 3-colorable planar graphs have an intersection segment representation using 3 slopes
  28. Hubie Chen, Radu Curticapean and Holger Dell. The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms
  29. Martin Milanič and Nevena Pivač. Minimal separators in graph classes defined by small forbidden induced subgraphs