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

DOI10.1007/3-540-60084-1_66zbMATH Open1412.68166OpenAlexW1500067928MaRDI QIDQ4645170FDOQ4645170

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

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

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)

Cites Work

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

Cited In (3)

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

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)