Alexandru I. Tomescu

Inf. Process. Lett., January, 2024

2023

Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails.

[BibT_eX]

[DOI]

Massimo Equi

Theor. Comput. Sci., October, 2023

A safety framework for flow decomposition problems via integer linear programming.

[BibT_eX]

[DOI]

Bioinform., October, 2023

Chaining for accurate alignment of erroneous long reads to acyclic variation graphs.

[BibT_eX]

[DOI]

Bioinform., August, 2023

On the Complexity of String Matching for Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, July, 2023

Algorithms and Complexity on Indexing Founder Graphs.

[BibT_eX]

[DOI]

Algorithmica, June, 2023

Flow Decomposition With Subpath Constraints.

[BibT_eX]

[DOI]

Lucia Williams

Brendan Mumey

IEEE ACM Trans. Comput. Biol. Bioinform., 2023

Minimum Path Cover: The Power of Parameterization.

[BibT_eX]

[DOI]

CoRR, 2023

Cut Paths and Their Remainder Structure, with Applications.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Genome-Scale Algorithm Design: Bioinformatics in the Era of High-Throughput Sequencing (2nd edition).

[BibT_eX]

[DOI]

Cambridge University Press, ISBN: 9781009341233, 2023

2022

Safety in Multi-Assembly via Paths Appearing in All Path Covers of a DAG.

[BibT_eX]

[DOI]

IEEE ACM Trans. Comput. Biol. Bioinform., 2022

Improving RNA Assembly via Safety and Completeness in Flow Decompositions.

[BibT_eX]

[DOI]

J. Comput. Biol., 2022

Efficient Minimum Flow Decomposition via Integer Linear Programming.

[BibT_eX]

[DOI]

J. Comput. Biol., 2022

Minimum Path Cover in Parameterized Linear Time.

[BibT_eX]

[DOI]

CoRR, 2022

Minimum Flow Decomposition in Graphs with Cycles using Integer Linear Programming.

[BibT_eX]

[DOI]

CoRR, 2022

Solving String Problems on Graphs Using the Labeled Direct Product.

[BibT_eX]

[DOI]

Nicola Rizzo

Algorithmica, 2022

Safety in s-t Paths, Trails and Walks.

[BibT_eX]

[DOI]

Algorithmica, 2022

Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Safety and Completeness in Flow Decompositions for RNA Assembly.

[BibT_eX]

[DOI]

Proceedings of the Research in Computational Molecular Biology, 2022

Fast, Flexible, and Exact Minimum Flow Decompositions via ILP.

[BibT_eX]

[DOI]

Proceedings of the Research in Computational Molecular Biology, 2022

Width Helps and Hinders Splitting Flows.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

Optimizing Safe Flow Decompositions in DAGs.

[BibT_eX]

[DOI]

Shahbaz Khan

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

A simplified algorithm computing all s-t bridges and articulation points.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2021

The Labeled Direct Product Optimally Solves String Problems on Graphs.

[BibT_eX]

[DOI]

Nicola Rizzo

CoRR, 2021

Safety of Flow Decompositions in DAGs.

[BibT_eX]

[DOI]

Shahbaz Khan

CoRR, 2021

A Linear-Time Parameterized Algorithm for Computing the Width of a DAG.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2021

Algorithms and Complexity on Indexing Elastic Founder Graphs.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Algorithms and Computation, 2021

Genome Assembly, from Practice to Theory: Safe, Complete and Linear-Time.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Genome assembly, a universal theoretical framework: unifying and generalizing the safe and complete algorithms.

[BibT_eX]

[DOI]

CoRR, 2020

On the parameterized complexity of the Minimum Path Cover problem in DAGs.

[BibT_eX]

[DOI]

CoRR, 2020

Computing all s-t bridges and articulation points simplified.

[BibT_eX]

[DOI]

CoRR, 2020

From omnitigs to macrotigs: a linear-time algorithm for safe walks - common to all closed arc-coverings of a directed graph.

[BibT_eX]

[DOI]

CoRR, 2020

Conditional Indexing Lower Bounds Through Self-Reducibility.

[BibT_eX]

[DOI]

Massimo Equi

CoRR, 2020

Linear Time Construction of Indexable Founder Block Graphs.

[BibT_eX]

[DOI]

Proceedings of the 20th International Workshop on Algorithms in Bioinformatics, 2020

2019

Safely Filling Gaps with Partial Solutions Common to All Solutions.

[BibT_eX]

[DOI]

Leena Salmela

IEEE ACM Trans. Comput. Biol. Bioinform., 2019

Hardness of Covering Alignment: Phase Transition in Post-Sequence Genomics.

[BibT_eX]

[DOI]

IEEE ACM Trans. Comput. Biol. Bioinform., 2019

Sparse Dynamic Programming on DAGs with Small Width.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2019

An Optimal O(nm) Algorithm for Enumerating All Walks Common to All Closed Edge-covering Walks of a Graph.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2019

Faster FPTASes for counting and random generation of Knapsack solutions.

[BibT_eX]

[DOI]

Inf. Comput., 2019

On the Complexity of Exact Pattern Matching in Graphs: Determinism and Zig-Zag Matching.

[BibT_eX]

[DOI]

CoRR, 2019

MIPUP: minimum perfect unmixed phylogenies for multi-sampled tumors via branchings and ILP.

[BibT_eX]

[DOI]

Bioinform., 2019

Safe and Complete Algorithms for Dynamic Programming Problems, with an Application to RNA Folding.

[BibT_eX]

[DOI]

Niko Kiirala

Leena Salmela

Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching, 2019

2018

Complexity and Algorithms for Finding a Perfect Phylogeny from Mixed Tumor Samples.

[BibT_eX]

[DOI]

IEEE ACM Trans. Comput. Biol. Bioinform., 2018

Perfect Phylogenies via Branchings in Acyclic Digraphs and a Generalization of Dilworth's Theorem.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2018

A safe and complete algorithm for metagenomic assembly.

[BibT_eX]

[DOI]

Nidia Obscura Acosta

Algorithms Mol. Biol., 2018

Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended.

[BibT_eX]

[DOI]

Proceedings of the Research in Computational Molecular Biology, 2018

2017

Set-syllogistics meet combinatorics.

[BibT_eX]

[DOI]

Math. Struct. Comput. Sci., 2017

Safe and Complete Contig Assembly Through Omnitigs.

[BibT_eX]

[DOI]

Paul Medvedev

J. Comput. Biol., 2017

Interval scheduling maximizing minimum coverage.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2017

Speeding up Dynamic Programming on DAGs through a Fast Approximation of Path Cover.

[BibT_eX]

[DOI]

CoRR, 2017

The minimum conflict-free row split problem revisited: a branching formulation and (in)approximability issues.

[BibT_eX]

[DOI]

CoRR, 2017

The Minimum Conflict-Free Row Split Problem Revisited.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2017

Optimal Omnitig Listing for Safe and Complete Contig Assembly.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

On Sets and Graphs: Perspectives on Logic and Combinatorics

[BibT_eX]

[DOI]

Springer, ISBN: 978-3-319-54980-4, 2017

2016

Graph operations on parity games and polynomial-time algorithms.

[BibT_eX]

[DOI]

Christoph Dittmann

Stephan Kreutzer

Theor. Comput. Sci., 2016

Gap Filling as Exact Path Length Problem.

[BibT_eX]

[DOI]

J. Comput. Biol., 2016

Safe and Complete Contig Assembly Via Omnitigs.

[BibT_eX]

[DOI]

Paul Medvedev

Proceedings of the Research in Computational Molecular Biology - 20th Annual Conference, 2016

MetaFlow: Metagenomic Profiling Based on Whole-Genome Coverage Analysis with Min-Cost Flows.

[BibT_eX]

[DOI]

Ahmed Sobih

Proceedings of the Research in Computational Molecular Biology - 20th Annual Conference, 2016

On using Longer RNA-seq Reads to Improve Transcript Prediction Accuracy.

[BibT_eX]

[DOI]

Proceedings of the 9th International Joint Conference on Biomedical Engineering Systems and Technologies (BIOSTEC 2016), 2016

2015

Explaining a Weighted DAG with Few Paths for Solving Genome-Guided Multi-Assembly.

[BibT_eX]

[DOI]

IEEE ACM Trans. Comput. Biol. Bioinform., 2015

Set Graphs. V. On representing graphs as membership digraphs.

[BibT_eX]

[DOI]

J. Log. Comput., 2015

Enumeration of the adjunctive hierarchy of hereditarily finite sets.

[BibT_eX]

[DOI]

Giorgio Audrito

Stephan G. Wagner

J. Log. Comput., 2015

Mapping Sets and Hypersets into Numbers.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2015

Interval scheduling maximizing minimum coverage.

[BibT_eX]

[DOI]

CoRR, 2015

SNV-PPILP: refined SNV calling for tumor data using perfect phylogenies and ILP.

[BibT_eX]

[DOI]

Karen E. van Rens

Bioinform., 2015

Finding a Perfect Phylogeny from Mixed Tumor Samples.

[BibT_eX]

[DOI]

Proceedings of the Algorithms in Bioinformatics - 15th International Workshop, 2015

Genome-Scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing.

[BibT_eX]

[DOI]

Cambridge University Press, ISBN: 9781107078536, 2015

2014

Set graphs. II. Complexity of set graph recognition and similar problems.

[BibT_eX]

[DOI]

Martin Milanic

Theor. Comput. Sci., 2014

Motif matching using gapped patterns.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2014

Set Graphs. III. Proof Pearl: Claw-Free Graphs Mirrored into Transitive Hereditarily Finite Sets.

[BibT_eX]

[DOI]

J. Autom. Reason., 2014

Set graphs. IV. Further connections with claw-freeness.

[BibT_eX]

[DOI]

Martin Milanic

Discret. Appl. Math., 2014

On the complexity of Minimum Path Cover with Subpath Constraints for multi-assembly.

[BibT_eX]

[DOI]

BMC Bioinform., 2014

Hyper-Extensionality and One-Node Elimination on Membership Graphs.

[BibT_eX]

[DOI]

Proceedings of the 29th Italian Conference on Computational Logic, 2014

The Representation of Boolean Algebras in the Spotlight of a Proof Checker.

[BibT_eX]

[DOI]

Proceedings of the 29th Italian Conference on Computational Logic, 2014

2013

Ranking, unranking and random generation of extensional acyclic digraphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2013

Well-quasi-ordering hereditarily finite sets.

[BibT_eX]

[DOI]

Int. J. Comput. Math., 2013

Set graphs. I. Hereditarily finite sets and extensional acyclic orientations.

[BibT_eX]

[DOI]

Martin Milanic

Discret. Appl. Math., 2013

Floating-point arithmetic for approximate counting and random generation problems.

[BibT_eX]

[DOI]

CoRR, 2013

Enumeration of the adjunctive hierarchy of hereditarily finite sets.

[BibT_eX]

[DOI]

Giorgio Audrito

CoRR, 2013

A novel min-cost flow method for estimating transcript expression with RNA-Seq.

[BibT_eX]

[DOI]

BMC Bioinform., 2013

Markov chain algorithms for generating sets uniformly at random.

[BibT_eX]

[DOI]

Ars Math. Contemp., 2013

A Novel Combinatorial Method for Estimating Transcript Expression with RNA-Seq: Bounding the Number of Paths.

[BibT_eX]

[DOI]

Proceedings of the Algorithms in Bioinformatics - 13th International Workshop, 2013

Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2013

A Proof-checking Experiment on Representing Graphs as Membership Digraphs.

[BibT_eX]

[DOI]

Pierpaolo Calligaris

Proceedings of the 28th Italian Conference on Computational Logic, 2013

2012

Sets as graphs.

[BibT_eX]

[DOI]

PhD thesis, 2012

Infinity, in short.

[BibT_eX]

[DOI]

J. Log. Comput., 2012

A randomized Numerical Aligner (rNA).

[BibT_eX]

[DOI]

Francesco Vezzi

J. Comput. Syst. Sci., 2012

A simpler proof for vertex-pancyclicity of squares of connected claw-free graphs.

[BibT_eX]

[DOI]

Discret. Math., 2012

rNA: a fast and accurate short reads numerical aligner.

[BibT_eX]

[DOI]

Bioinform., 2012

2011

Counting extensional acyclic digraphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2011

Computing the Maximum Bisimulation with Spiking Neural P Systems.

[BibT_eX]

[DOI]

Proceedings of the Computation, 2011

2010

On cycles through two arcs in strong multipartite tournaments

[BibT_eX]

[DOI]

CoRR, 2010

2008

Implementing Sorting Networks with Spiking Neural P Systems.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2008

Unicyclic and bicyclic graphs having minimum degree distance.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2008

2007

Simulating the Bitonic Sort Using P Systems.

[BibT_eX]

[DOI]

Mario J. Pérez-Jiménez