research
∙
09/21/2023
Recognizing unit multiple intervals is hard
Multiple interval graphs are a well-known generalization of interval gra...
share
research
∙
11/17/2022
Minimum Path Cover in Parameterized Linear Time
A minimum path cover (MPC) of a directed acyclic graph (DAG) G = (V,E) i...
research
∙
10/21/2022
Solving the Probabilistic Profitable Tour Problem on a Tree
The profitable tour problem (PTP) is a well-known NP-hard routing proble...
research
∙
10/14/2022
Cut paths and their remainder structure, with applications
In a strongly connected graph G = (V,E), a cut arc (also called strong b...
research
∙
07/05/2022
Width Helps and Hinders Splitting Flows
Minimum flow decomposition (MFD) is the NP-hard problem of finding a sma...
research
∙
07/12/2021
Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time
A minimum path cover (MPC) of a directed acyclic graph (DAG) G = (V,E) i...
research
∙
07/08/2021
Algorithmic aspects of quasi-kernels
In a digraph, a quasi-kernel is a subset of vertices that is independent...
research
∙
11/25/2020
Genome assembly, a universal theoretical framework: unifying and generalizing the safe and complete algorithms
Genome assembly is a fundamental problem in Bioinformatics, requiring to...
research
∙
07/15/2020
On the parameterized complexity of the Minimum Path Cover problem in DAGs
A minimum path cover (MPC) of a directed acyclic graph (DAG) G = (V,E) i...
research
∙
07/09/2020
Safety in s-t Paths, Trails and Walks
Given a directed graph G and a pair of nodes s and t, an s-t bridge of G...
research
∙
06/26/2020
Computing all s-t bridges and articulation points simplified
Given a directed graph G and a pair of nodes s and t, an s-t bridge of G...
research
∙
02/24/2020
From omnitigs to macrotigs: a linear-time algorithm for safe walks – common to all closed arc-coverings of a directed graph
A partial solution to a problem is called safe if it appears in all solu...
research
∙
08/24/2019
When a Dollar Makes a BWT
The Burrows-Wheeler-Transform (BWT) is a reversible string transformatio...
research
∙
05/06/2018
On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier
In 2005 Kumar studied the Restricted Disjunctive Temporal Problem (RDTP)...
research
∙
05/04/2015
Dynamic Consistency of Conditional Simple Temporal Networks via Mean Payoff Games: a Singly-Exponential Time DC-Checking
Conditional Simple Temporal Network (CSTN) is a constraint-based graph-f...
research
∙
03/13/2015