A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant

DOI10.1007/978-3-540-78773-0_29zbMATH Open1136.90520OpenAlexW1571879181MaRDI QIDQ5458540FDOQ5458540

Yoshiko Wakabayashi, Cristina G. Fernandes, Christian Tjandraatmadja, Carlos E. Ferreira

Publication date: 15 April 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_29

Recommendations

• A branch-and-cut approach to the repetition-free longest common subsequence problem
• Repetition-free longest common subsequence
• Repetition-free longest common subsequence
• On the parameterized complexity of the repetition free longest common subsequence problem
• Exact algorithms for the repetition-bounded longest common subsequence problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Cites Work

• Introduction to algorithms
• Geometric algorithms and combinatorial optimization
• Normal hypergraphs and the perfect graph conjecture
• The ellipsoid method and its consequences in combinatorial optimization
• On certain polytopes associated with graphs
• Repetition-free longest common subsequence
• Anti-blocking polyhedra
• Exemplar Longest Common Subsequence

Cited In (6)

• A linear space algorithm for the LCS problem
• Variants of constrained longest common subsequence
• A dynamic programming solution to a generalized LCS problem
• Repetition-free longest common subsequence
• A hybrid genetic algorithm for the repetition free longest common subsequence problem
• A branch-and-cut approach to the repetition-free longest common subsequence problem

This page was built for publication: A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant

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