Complexity results and algorithms for representing paths in digraphs

DOI10.1016/J.TCS.2026.115770MaRDI QIDQ6851436zbMATH OpenFDO

Authors Riccardo Dondi, Alexandru Popa

Publication date 27 February 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115770

zbMATH Keywords

algorithmscomputational complexitygraph string matchingparameterized complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A combinatorial problem in geometry.
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A simplified NP-complete satisfiability problem
• Color-coding
• Computational graph pangenomics: a tutorial on data structures and their applications
• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 7646025 (Why is no real title available?)
• Improved approximate pattern matching on hypertext
• On approximating the longest path in a graph
• On the complexity of approximately matching a string to a directed graph
• On the complexity of sequence to graph alignment
• On the Complexity of String Matching for Graphs
• On the parameterized complexity of multiple-interval graph problems
• Pattern Matching in Hypertext
• Some optimal inapproximability results
• The design of approximation algorithms
• The longest letter-duplicated subsequence and related problems
• The longest subsequence-repeated subsequence problem

This page was built for publication: Complexity results and algorithms for representing paths in digraphs

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