Buchbeiträge

• Richard Karp, Till Nierhoff, Till Tantau:
  Optimal Flow Distribution Among Multiple Channels with Unknown Capacities.
  In Essays in Theoretical Computer Science in Memory of Shimon Even, Band 3895 von Lecture Notes in Computer Science - Festschriften, S. 111-128. Springer, 2006.
  Zusammenfassung anzeigen
  
  Consider a simple network flow problem in which a flow of value D must be split among n channels directed from a source to a sink. The initially unknown channel capacities can be probed by attempting to send a flow of at most D units through the network. If the flow is not feasible, we are told on which channels the capacity was exceeded (binary feedback) and possibly also how many units of flow were successfully sent on these channels (throughput feedback). For throughput feedback we present optimal protocols for minimizing the number of rounds needed to find a feasible flow and for minimizing the total amount of wasted flow. For binary feedback we present an asymptotically optimal protocol.
• Jens Gramm, Arfst Nickelsen, Till Tantau:
  Fixed-Parameter Algorithms in Phylogenetics.
  In Bioinformatics: Volume I: Data, Sequence Analysis and Evolution, Band 452 von Methods in Molecular Biology, S. 507-535. Springer, 2008.
  Zusammenfassung anzeigen
  
  We survey the use of fixed-parameter algorithms in phylogenetics. A central computational problem in this field is the construction of a likely phylogeny (genealogical tree) for a set of species based on observed differences in the phenotype, on differences in the genotype, or on given partial phylogenies. Ideally, one would like to construct so-called perfect phylogenies, which arise from an elementary evolutionary model, but in practice one must often be content with phylogenies whose "distance from perfection" is as small as possible. The computation of phylogenies also has applications in seemingly unrelated areas such as genomic sequencing and finding and understanding genes. The numerous computational problems arising in phylogenetics are often NP-complete, but for many natural parametrizations they can be solved using fixed-parameter algorithms.
• Till Tantau:
  Der One-Time-Pad-Algorithmus.
  In Taschenbuch der Algorithmen, Springer, 2008.
  Zusammenfassung anzeigen
  
  Ein Beitrag über den One-Time-Pad-Algorithmus im Rahmen der Algorithmen der Woche während des Jahrs der Informatik 2006.