Browsing Bergen Open Research Archive by Author "Arrighi, Emmanuel"

Now showing items 1-3 of 3

    • Order-Related Problems Parameterized by Width 

      Arrighi, Emmanuel (Doctoral thesis, 2022-05-25)
      In the main body of this thesis, we study two different order theoretic problems. The first problem, called Completion of an Ordering, asks to extend a given finite partial order to a complete linear order while respecting ...

    • Three Is Enough for Steiner Trees 

      Arrighi, Emmanuel; De Oliveira Oliveira, Mateus (Journal article; Peer reviewed, 2021)
      In the Steiner tree problem, the input consists of an edge-weighted graph G together with a set S of terminal vertices. The goal is to find a minimum weight tree in G that spans all terminals. This fundamental NP-hard ...

    • Width Notions for Ordering-Related Problems 

      Arrighi, Emmanuel; Fernau, Henning; De Oliveira Oliveira, Mateus; Wolf, Petra (Journal article; Peer reviewed, 2020)
      We are studying a weighted version of a linear extension problem, given some finite partial order ρ, called Completion of an Ordering. While this problem is NP-complete, we show that it lies in FPT when parameterized by ...