Finding diverse strings and longest common subsequences in a graph

DOI10.4230/LIPICS.CPM.2024.27MaRDI QIDQ6891067zbMATH OpenFDO

Authors Yuto Shida, Giulia Punzi, Yasuaki Kobayashi, Takeaki Uno, Hiroki Arimura

Publication date 2 December 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CPM.2024.27

zbMATH Keywords

dispersionHamming distanceapproximation algorithmslongest common subsequenceparameterized complexitysequence analysis

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• scientific article; zbMATH DE number 7646025 (Why is no real title available?)
• A compact DAG for storing and searching maximal common subsequences
• A study on two geometric location problems
• An FPT-algorithm for longest common subsequence parameterized by the maximum number of deletions
• An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs
• An improved analysis of local search for max-sum diversification
• Approximation algorithms for dispersion problems
• Color-coding
• Diversity of solutions: an exploration through the lens of fixed-parameter tractability theory
• Efficient methods for multiple sequence alignment with guaranteed error bounds
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Geometry of cuts and metrics
• Heuristic and Special Case Algorithms for Dispersion Problems
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Matching Sequences under Deletion/Insertion Constraints
• Parameterized algorithms
• Parametrized complexity theory.
• Structure preserving reductions among convex optimization problems
• The Complexity of Some Problems on Subsequences and Supersequences
• The String-to-String Correction Problem
• The discrete p-dispersion problem
• The normalized edit distance with uniform operation costs is a metric
• The parameterized complexity of sequence alignment and consensus
• The string edit distance matching problem with moves
• \(L_{1}\) pattern matching lower bound

This page was built for publication: Finding diverse strings and longest common subsequences in a graph

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