A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant | SpringerLink
Skip to main content
Springer Nature Link
Log in

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

  • Conference paper
LATIN 2008: Theoretical Informatics (LATIN 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4957))

Included in the following conference series:

  • 1721 Accesses

Abstract

We consider the longest common subsequence problem (lcs) and a variant of it where each symbol may occur at most once in the common subsequence. The lcs is a well-known problem that can be solved in polynomial time by a dynamic programming algorithm. We provide a complete description of a polytope we associate with the lcs. The integrality of this polytope can be derived by showing that it is in fact the clique polytope of a perfect graph. The repetition-free version of the problem is known to be difficult. We also associate a polytope with this version and investigate its facial structure. We present some valid and facet-defining inequalities for this polytope and discuss separation procedures. Finally, we present some computational results of a branch and cut algorithm we have implemented for this problem.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Adi, S.S., Braga, M., Fernandes, C.G., Ferreira, C.E., Martinez, F.H.V., Sagot, M.-F., Stefanes, M.A., Tjandraatmadja, C., Wakabayashi, Y.: Repetition-free longest common subsequence. In: Proc. IV Latin-American Algorithms, Graphs and Optimization Symposium (to appear) (2007)

    Google Scholar 

  2. Bonizzoni, P., Della Vedova, G., Dondi, R., Fertin, G., Vialette, S.: Exemplar longest common subsequence. In: Alexandrov, V.N., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds.) ICCS 2006. LNCS, vol. 3992, pp. 622–629. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  3. Chvátal, V.: On certain polytopes associated with graphs. J. Combinatorial Theory Ser. B 18, 138–154 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  4. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)

    MATH  Google Scholar 

  5. Fulkerson, D.R.: Anti-blocking polyhedra. J. Combinatorial Theory Ser. B 12, 50–71 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  6. Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169–197 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  7. Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg (1988)

    MATH  Google Scholar 

  8. Lovász, L.: Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2(3), 253–267 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  9. Sankoff, D.: Genome rearrangement with gene families. Bioinformatics 15(11), 909–917 (1999)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universidade de São Paulo, Brazil

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

Authors
  1. Cristina G. Fernandes
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carlos E. Ferreira
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Christian Tjandraatmadja
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yoshiko Wakabayashi
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Eduardo Sany Laber Claudson Bornstein Loana Tito Nogueira Luerbio Faria

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Fernandes, C.G., Ferreira, C.E., Tjandraatmadja, C., Wakabayashi, Y. (2008). A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_29

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-78773-0_29

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-78772-3

  • Online ISBN: 978-3-540-78773-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation