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

DOI10.1007/978-3-540-78773-0_29MaRDI QIDQ5458540zbMATH OpenOpenAlexFDO

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

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

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(6)

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

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)