Zobrazeno 1 - 10
of 127
pro vyhledávání: '"TOMESCU, P. I."'
Autor:
Sena, Francisco, Tomescu, Alexandru I.
A common step at the core of many RNA transcript assembly tools is to find a set of weighted paths that best explain the weights of a DAG. While such problems easily become NP-hard, scalable solvers exist only for a basic error-free version of this p
Externí odkaz:
http://arxiv.org/abs/2411.03871
Minimum flow decomposition (MFD) is the strongly NP-hard problem of finding a smallest set of integer weighted paths in a graph $G$ whose weighted sum is equal to a given flow $f$ on $G$. Despite its many practical applications, we lack an understand
Externí odkaz:
http://arxiv.org/abs/2409.20278
Autor:
Grigorjew, Andreas, Dias, Fernando H. C., Cracco, Andrea, Rizzi, Romeo, Tomescu, Alexandru I.
Given a flow network, the Minimum Flow Decomposition (MFD) problem is finding the smallest possible set of weighted paths whose superposition equals the flow. It is a classical, strongly NP-hard problem that is proven to be useful in RNA transcript a
Externí odkaz:
http://arxiv.org/abs/2311.10563
Computing a minimum path cover (MPC) of a directed acyclic graph (DAG) is a fundamental problem with a myriad of applications, including reachability. Although it is known how to solve the problem by a simple reduction to minimum flow, recent theoret
Externí odkaz:
http://arxiv.org/abs/2308.08960
Autor:
Dias, Fernando H. C., Caceres, Manuel, Williams, Lucia, Mumey, Brendan, Tomescu, Alexandru I.
Many important problems in Bioinformatics (e.g., assembly or multi-assembly) admit multiple solutions, while the final objective is to report only one. A common approach to deal with this uncertainty is finding safe partial solutions (e.g., contigs)
Externí odkaz:
http://arxiv.org/abs/2301.13245
A minimum path cover (MPC) of a directed acyclic graph (DAG) $G = (V,E)$ is a minimum-size set of paths that together cover all the vertices of the DAG. Computing an MPC is a basic polynomial problem, dating back to Dilworth's and Fulkerson's results
Externí odkaz:
http://arxiv.org/abs/2211.09659
Autor:
Cairo, Massimo, Khan, Shahbaz, Rizzi, Romeo, Schmidt, Sebastian, Tomescu, Alexandru I., Zirondelli, Elia C.
In a strongly connected graph $G = (V,E)$, a cut arc (also called strong bridge) is an arc $e \in E$ whose removal makes the graph no longer strongly connected. Equivalently, there exist $u,v \in V$, such that all $u$-$v$ walks contain $e$. Cut arcs
Externí odkaz:
http://arxiv.org/abs/2210.07530
Minimum flow decomposition (MFD) -- the problem of finding a minimum set of weighted source-to-sink paths that perfectly decomposes a flow -- is a classical problem in Computer Science, and variants of it are powerful models in different fields such
Externí odkaz:
http://arxiv.org/abs/2209.00042
An Eulerian circuit in a directed graph is one of the most fundamental Graph Theory notions. Detecting if a graph $G$ has a unique Eulerian circuit can be done in polynomial time via the BEST theorem by de Bruijn, van Aardenne-Ehrenfest, Smith and Tu
Externí odkaz:
http://arxiv.org/abs/2208.08522
Autor:
Cáceres, Manuel, Cairo, Massimo, Grigorjew, Andreas, Khan, Shahbaz, Mumey, Brendan, Rizzi, Romeo, Tomescu, Alexandru I., Williams, Lucia
Minimum flow decomposition (MFD) is the NP-hard problem of finding a smallest decomposition of a network flow/circulation $X$ on a directed graph $G$ into weighted source-to-sink paths whose superposition equals $X$. We show that, for acyclic graphs,
Externí odkaz:
http://arxiv.org/abs/2207.02136