Blar i Department of Informatics på forfatter "Ordyniak, Sebastian"

Viser treff 1-2 av 2

    • Towards a Polynomial Kernel for Directed Feedback Vertex Set 

      Bergougnoux, Benjamin; Eiben, Eduard; Ganian, Robert; Ordyniak, Sebastian; Ramanujan, M. S. (Journal article; Peer reviewed, 2020)
      In the DIRECTED FEEDBACK VERTEX SET (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. ...

    • Treewidth is NP-Complete on Cubic Graphs 

      Bodlaender, Hans L.; Bonnet, Édouard; Jaffke, Lars; Knop, Dusan; Lima, Paloma Thome de; Milanič, Martin; Ordyniak, Sebastian; Pandey, Sukanya; Suchy, Ondrey (Journal article; Peer reviewed, 2023)
      In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new ...