NC algorithms for finding a maximal set of paths with application to compressing strings

DOI10.1007/3-540-60084-1_66MaRDI QIDQ4645170zbMATH OpenOpenAlexFDO

Authors Zhi-Zhong Chen

Publication date 10 January 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60084-1_66

zbMATH Keywords

approximation algorithmHamiltonian pathundirected graphapproximation ratiocompression ratio

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Parallel algorithms in computer science (68W10)

Recommendations

• Fast RNC and NC algorithms for maximal path sets
• Sublinear algorithms for approximating string compressibility
• Sublinear Algorithms for Approximating String Compressibility
• Compressing optimal paths with run length encoding
• -Algorithms for Minimum Link Path and Related Problems
• Algorithmics on SLP-compressed strings: a survey
• On extensions of maximal repeats in compressed strings
• ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS
• NC algorithms for dynamically solving the all pairs shortest paths problem and related problems
• Optimal partitions of strings: a new class of Burrows-Wheeler compression algorithms

Cites work

• A greedy approximation algorithm for constructing shortest common superstrings
• Approximation algorithms for the shortest common superstring problem
• On finding minimal length superstrings
• Sequential and Parallel Approximation of Shortest Superstrings

Cited in

(3)

• Parallel and sequential approximation of shortest superstrings
• Fast RNC and NC algorithms for maximal path sets
• Fast RNC and NC algorithms for finding a maximal set of paths with an application

This page was built for publication: NC algorithms for finding a maximal set of paths with application to compressing strings

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