Browsing Department of Informatics by Subject "Exact algorithms"

Now showing items 1-2 of 2

    • A Note on Exact Algorithms for Vertex Ordering Problems on Graphs 

      Bodlaender, Hans L.; Fomin, Fedor; Koster, Arie M.C.A.; Kratsch, Dieter; Thilikos, Dimitrios M. (Peer reviewed; Journal article, 2011-01-21)
      In this note, we give a proof that several vertex ordering problems can be solved in O ∗(2 n ) time and O ∗(2 n ) space, or in O ∗(4 n ) time and polynomial space. The algorithms generalize algorithms for the Travelling ...

    • Solving the 2-disjoint connected subgraphs problem faster than 2ⁿ 

      Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michal Pawel; Wojtaszczyk, Jakub Onufry (Peer reviewed; Journal article, 2014-10)
      The 2-DISJOINT CONNECTED SUBGRAPHS problem, given a graph along with two disjoint sets of terminals Z1,Z2, asks whether it is possible to find disjoint sets A1,A2, such that Z1 ⊆ A1, Z2 ⊆ A2 and A1,A2 induce connected ...