Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 1 von 1
Zurück zur Trefferliste

Polyhedral Aspects of Self-Avoiding Walks

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-12576
  • In this paper, we study self-avoiding walks of a given length on a graph. We consider a formulation of this problem as a binary linear program. We analyze the polyhedral structure of the underlying polytope and describe valid inequalities. Proofs for their facial properties for certain special cases are given. In a variation of this problem one is interested in optimal configurations, where an energy function measures the benefit if certain path elements are placed on adjacent vertices of the graph. The most prominent application of this problem is the protein folding problem in biochemistry. On a set of selected instances, we demonstrate the computational merits of our approach.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Agnes Dittel, Armin Fügenschuh, Alexander Martin
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:
MSC-Klassifikation:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C38 Paths and cycles [See also 90B10]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
92-XX BIOLOGY AND OTHER NATURAL SCIENCES / 92Dxx Genetics and population dynamics / 92D20 Protein sequences, DNA sequences
Datum der Erstveröffentlichung:11.04.2011
Schriftenreihe (Bandnummer):ZIB-Report (11-11)
ZIB-Reportnummer:11-11
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.