• P3 problem and Magnolia language: Specializing array computations for emerging architectures 

      Chetioui, Benjamin; Larnøy, Marius Kleppe; Järvi, Jaakko Timo Henrik; Haveraaen, Magne; Mullin, Lenore (Journal article; Peer reviewed, 2022)
      The problem of producing portable high-performance computing (HPC) software that is cheap to develop and maintain is called the P3 (performance, portability, productivity) problem. Good solutions to the P3 problem have ...
    • Packing arc-disjoint cycles in tournaments 

      Bessy, Stephane; Bougeret, Marin; Krithika, R; Sahu, Abhishek; Saurabh, Saket; Thiebaut, Jocelyn; Zehavi, Meirav (Journal article; Peer reviewed, 2019)
      A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining ...
    • Packing cycles faster than Erdos-Posa 

      Lokshtanov, Daniel; Mouawad, Amer E.; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2019)
      The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertex-disjoint cycles. Since the publication of the classic Erdös--Pósa theorem in 1965, this problem received significant attention ...
    • Parallel algorithms for computing k-connectivity 

      Haakonsen, Joachim (Master thesis, 2017-05-05)
    • Parallel algorithms for matching under preference 

      Lerring, Håkon Heggernes (Master thesis, 2017-06-20)
    • Parallel Graph Algorithms for Combinatorial Scientific Computing 

      Patwary, Mostofa Ali (Doctoral thesis, 2011-08-26)
    • Parallel Matching and Clustering Algorithms on GPUs 

      Naim, Md. (Doctoral thesis, 2017-06-17)
    • Parameter optimisation for the improved modelling of industrial-scale gas explosions 

      Both, Anna-Lena (Doctoral thesis, 2019-06-17)
      This thesis presents work on improving the predictive capabilities of a numerical model by parameter optimisation. The numerical model is based on computational fluid dynamics (CFD) and predicts the consequences of ...
    • Parameterization Above a Multiplicative Guarantee 

      Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)
      Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given ...
    • Parameterized complexity classification of deletion to list matrix-partition for low-order matrices 

      Agrawal, Akanksha; Kolay, Sudeshna; Madathil, Jayakrishnan; Saurabh, Saket (Journal article; Peer reviewed, 2019)
      Given a symmetric l x l matrix M=(m_{i,j}) with entries in {0,1,*}, a graph G and a function L : V(G) - > 2^{[l]} (where [l] = {1,2,...,l}), a list M-partition of G with respect to L is a partition of V(G) into l parts, ...
    • Parameterized Complexity of Broadcasting in Graphs 

      Fomin, Fedor; Pierre, Fraigniaud; Golovach, Petr (Journal article; Peer reviewed, 2023)
      The task of the broadcast problem is, given a graph G and a source vertex s, to compute the minimum number of rounds required to disseminate a piece of information from s to all vertices in the graph. It is assumed that, ...
    • Parameterized complexity of categorical clustering with size constraints 

      Fomin, Fedor; Golovach, Petr; Purohit, Nidhi (Journal article; Peer reviewed, 2023)
    • Parameterized complexity of conflict-free matchings and paths 

      Agrawal, Akanksha; Jain, Pallavi; Kanesh, Lawqueen; Saurabh, Saket (Journal article; Peer reviewed, 2019)
      An input to a conflict-free variant of a classical problem Gamma, called Conflict-Free Gamma, consists of an instance I of Gamma coupled with a graph H, called the conflict graph. A solution to Conflict-Free Gamma in (I,H) ...
    • Parameterized Complexity of Directed Spanner Problems 

      Fomin, Fedor; Golovach, Petr; Lochet, William; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2020)
      We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance ...
    • Parameterized Complexity of Directed Spanner Problems 

      Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2021)
      We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance ...
    • Parameterized complexity of Eulerian deletion problems 

      Cygan, Marek; Pilipczuk, Marcin; Marx, Dániel; Pilipczuk, Michal Pawel; Schlotter, Ildikó (Peer reviewed; Journal article, 2014-01)
      We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity ...
    • Parameterized Complexity of Feature Selection for Categorical Data Clustering 

      Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Journal article; Peer reviewed, 2021)
      We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approaches to reduce dimensionality in practice, ...
    • The parameterized complexity of finding minimum bounded chains 

      Blaser, Nello; Brun, Morten; Salbu, Lars Moberg; Vågset, Erlend Raa (Journal article; Peer reviewed, 2024)
      Finding the smallest d-chain with a specific (d − 1)-boundary in a simplicial complex is known as the Minimum Bounded Chain problem (MBCd). MBCd is NP-hard for all d ≥2. In this paper, we prove that it is also W[1]-hard ...
    • The Parameterized Complexity of Guarding Almost Convex Polygons 

      Agrawal, Akanksha; Knudsen, Kristine Vitting Klinkby; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)
      The Art Gallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide ...
    • Parameterized complexity of PCA 

      Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Journal article; Peer reviewed, 2020)
      We discuss some recent progress in the study of Principal Component Analysis (PCA) from the perspective of Parameterized Complexity.