Encyclopedia of Algorithms

Herausgegeben von Kao, Ming-Yang

• Gebundenes Buch

Produktbeschreibung

The 2 nd ed. of this comprehensive work provides a set of solutions to important algorithmic problems for students and researchers interested in quickly locating useful information. The first edition of the reference focused on high-impact solutions from the most recent decade; this edition widens the scope of the work.

Nearly 500 entries are organized alphabetically by problem, with subentries allowing for distinct solutions and special cases to be listed by the year. An entry includes: a description of the basic algorithmic problem; the input and output specifications; the key results; examples of applications; citations to the key literature.

Open problems, links to downloadable code, experimental results, data sets, and illustrations are provided. All entries are written by experts with links to Internet sites that outline their research work. The entries are peer-reviewed.

This defining reference is published in print and on line. The print publication includes an index of subjects and authors as well as a chronology for locating recent solutions. The online edition supplements this index with hyperlinks and also includes hyperlinks in the text of the entries to related entries, xRefer citations, and other useful URLs mentioned above.

Produktdetails

• Verlag: Springer / Springer New York / Springer, Berlin
• Artikelnr. des Verlages: 978-1-4939-2863-7
• 2. Aufl.
• Seitenzahl: 2389
• Erscheinungstermin: 14. März 2016
• Englisch
• Abmessung: 260mm x 184mm x 146mm
• ISBN-13: 9781493928637
• ISBN-10: 1493928635
• Artikelnr.: 42665772

Autorenporträt

Ming-Yang  Kao is Professor of Computer Science at the Northwestern University, Evanston. He got a B.S. in Mathematics, 1978 at the National Taiwan University, Republic of China (Taiwan) and his Ph.D. in Computer Science, 1986, at Yale University, USA. Prof. Kao studies the design, analysis and implementation of algorithms. His work spans a broad range of applications including bioinformatics, computational finance, electronic commerce, and nanotechnology. Kao's most recent research includes work on DNA self-assembly, variants of the traveling salesman problem, and graph labeling problems. Kao heads the EECS Computing, Algorithms & Applications Division and is the editor-in-chief of Algorithmica.

Inhaltsangabe

From the contents: Abelian Hidden Subgroup Problem.- Abstract Voronoi Diagrams.- Active Learning - Modern Learning Theory.- Backdoors to SAT.- Backtracking Based k-SAT Algorithms.- Bargaining Networks.- Cache-Oblivious B-Tree.- Canonical Orders and Schnyder Realizers.- Circuit Placement.-Data Migration.- Decoding Reed-Solomon Codes.- Direct Routing Algorithms.- Edit Distance Under Block Operations.- Engineering Geometric Algorithms.- Enumeration of Non-crossing Geometric Graphs.- Facility Location.- Flow Time Minimization.- Force-Directed Graph Drawing.- Gate Sizing.- General Equilibrium.- Geographic Routing.- Hamilton Cycles in Random Intersection Graphs.- Hardness of Proper Learning.- Huffman Coding.- Implementation Challenge for Shortest Paths.- Incentive Compatible Selection.- Inductive Inference.- Kernelization, Bidimensionality and Kernels.- Kinetic Data Structures.- Knowledge in Distributed Systems.- Large-Treewidth Graph Decompositions.- Layout Decomposition for Multiple Patterning.- Learning Automata.- Majority Equilibrium.- Manifold Reconstruction.- Market Games and Content Distribution.- Nash Equilibria and Dominant Strategies in Routing.- Nearest Neighbor Interchange and Related Distances.- Negative Cycles in Weighted Digraphs.- Oblivious Routing.- Online Interval Coloring.- Online Paging and Caching.- PAC Learning.- Parity Games.- Permutation Enumeration.- Quadtrees and Morton Indexing.- Quantum Algorithm for Factoring.- Quantum Dense Coding.- Radiocoloring in Planar Graphs.- Random Planted 3-SAT.- Randomization in Distributed Computing.- Schedulers for Optimistic Rate Based Flow Control.- Secretary Problems and Online Auctions.- Separators in Graphs.- Table Compression.- Text Indexing.- Triangulation Data Structures.- Unified View of Graph Searching and LDFS-Based Certifying Algorithms.- Universal Sequencing on an Unreliable Machine.- Upward Graph Drawing.- Vector Bin Packing.- Vector Scheduling Problems.- Voltage Scheduling.- Wavelet Trees.- Well Separated Pair Decomposition.- Wire Sizing.