Algorithms and data structures

Más información sobre el libro

This collection encompasses a diverse range of topics in algorithm design and complexity. It includes studies on multi-party pseudo-telepathy, adapting triangulations with edge flips, and shape segmentation using flow discretization. The exploration of phylogenetic reconstruction from gene-rearrangement data highlights challenges in handling unequal gene content. Other significant areas cover optimal motif enumeration, scheduling problems in bureaucratic contexts, and bandwidth-constrained allocation in grid computing. The text also delves into algorithms for minimum lateness/tardiness scheduling, fast algorithms for temporal range queries, and distribution-sensitive binomial queues. Key discussions include optimal worst-case operations for implicit cache-oblivious search trees, extremal configurations in pseudoline arrangements, and fast relative approximation of potential fields. Additional topics address integrated prefetching and caching, online seat reservations, and routing algorithms for ring networks. The work presents approximation algorithms for various problems, such as rectilinear Steiner trees and hotlink assignments in web directories. It also examines dynamic text matching, geometric graph proximity structures, and improved bounds on Boolean matrix multiplication. The collection concludes with insights into parameterized complexity, compact visibility representation, and new challenges in algorithm design.