Linear time construction of indexable elastic founder graphs

DOI10.1007/978-3-031-06678-8_35OpenAlexW4285151990MaRDI QIDQ2169983FDOQ2169983

Authors: Nicola Rizzo, Veli Mäkinen 

Publication date: 30 August 2022

Full work available at URL: https://arxiv.org/abs/2201.06492

Recommendations

• Linear time construction of indexable founder block graphs
• Algorithms and complexity on indexing founder graphs
• scientific article; zbMATH DE number 7696008
• Optimal query complexity bounds for finding graphs
• scientific article
• On indexable graphs
• Embedding rectilinear graphs in linear time
• scientific article; zbMATH DE number 7301806
• An Almost Linear-Time Algorithm for Graph Realization
• Finding articulation points of large graphs in linear time

zbMATH Keywords

dynamic programmingdata structurespattern matchingsuffix treemultiple sequence alignmentsegmentation algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• On-line construction of suffix trees
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Title not available (Why is that?)
• Linear time construction of indexable founder block graphs

Cited In (2)

• Algorithms and complexity on indexing founder graphs
• Elastic founder graphs improved and enhanced

Uses Software

• HISAT
• vg

This page was built for publication: Linear time construction of indexable elastic founder graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2169983)