Parameterized Algorithms
暫譯: 參數化演算法

Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh

買這商品的人也買了...

商品描述

This comprehensive textbook presents a clean and coherent account of most fundamental tools and techniques in Parameterized Algorithms and is a self-contained guide to the area. The book covers many of the recent developments of the field, including application of important separators, branching based on linear programming, Cut & Count to obtain faster algorithms on tree decompositions, algorithms based on representative families of matroids, and use of the Strong Exponential Time Hypothesis. A number of older results are revisited and explained in a modern and didactic way.

The book provides a toolbox of algorithmic techniques. Part I is an overview of basic techniques, each chapter discussing a certain algorithmic paradigm. The material covered in this part can be used for an introductory course on fixed-parameter tractability. Part II discusses more advanced and specialized algorithmic ideas, bringing the reader to the cutting edge of current research. Part III presents complexity results and lower bounds, giving negative evidence by way of W[1]-hardness, the Exponential Time Hypothesis, and kernelization lower bounds.

All the results and concepts are introduced at a level accessible to graduate students and advanced undergraduate students. Every chapter is accompanied by exercises, many with hints, while the bibliographic notes point to original publications and related work.

商品描述(中文翻譯)

這本綜合性的教科書清晰且連貫地介紹了參數化演算法中大多數基本工具和技術,並且是該領域的自成一體的指南。書中涵蓋了該領域的許多最新發展,包括重要分隔器的應用、基於線性規劃的分支、使用 Cut & Count 獲得樹分解的更快演算法、基於代表性家族的矩陣演算法,以及強指數時間假設的使用。許多舊有的結果也以現代且教學的方式重新探討和解釋。

本書提供了一套演算法技術的工具箱。第一部分是基本技術的概述,每章討論一種特定的演算法範式。本部分所涵蓋的材料可用於固定參數可處理性(fixed-parameter tractability)的入門課程。第二部分討論更高級和專門的演算法思想,將讀者帶入當前研究的前沿。第三部分呈現複雜性結果和下界,通過 W[1]-困難性、指數時間假設和核心化下界提供負證據。

所有結果和概念都以研究生和高年級本科生可理解的水平介紹。每章都附有練習題,許多題目提供提示,而參考文獻則指向原始出版物和相關工作。