Parameterized Algorithms

این کتاب درسی جامع شرحی تمیز و منسجم از اکثر ابزارها و تکنیک های اساسی در الگوریتم های پارامتری شده ارائه می دهد و راهنمای مستقلی برای این منطقه است. این کتاب بسیاری از پیشرفت‌های اخیر این حوزه را پوشش می‌دهد، از جمله استفاده از جداکننده‌های مهم، انشعاب بر اساس برنامه‌ریزی خطی، Cut & Count برای به دست آوردن الگوریتم‌های سریع‌تر در تجزیه درخت، الگوریتم‌های مبتنی بر خانواده‌های نماینده ماتروئیدها، و استفاده از زمان نمایی قوی. فرضیه. تعدادی از نتایج قدیمی‌تر به روشی مدرن و آموزشی بازبینی و توضیح داده می‌شوند.

این کتاب جعبه ابزاری از تکنیک‌های الگوریتمی را ارائه می‌کند. بخش اول مروری بر تکنیک های اساسی است که هر فصل یک الگوریتمی خاص را مورد بحث قرار می دهد. مطالب پوشش داده شده در این بخش را می توان برای دوره مقدماتی تراکت پذیری با پارامتر ثابت استفاده کرد. بخش دوم ایده‌های الگوریتمی پیشرفته‌تر و تخصصی‌تری را مورد بحث قرار می‌دهد و خواننده را به لبه برش تحقیقات فعلی می‌رساند. بخش سوم نتایج پیچیدگی و کران‌های پایین‌تر را ارائه می‌کند، و شواهد منفی را از طریق W[1]-سختی، فرضیه زمان نمایی، و کران‌های پایین‌تر هسته‌سازی ارائه می‌دهد.

همه نتایج و مفاهیم در سطح قابل دسترسی معرفی شده‌اند. به دانشجویان تحصیلات تکمیلی و دانشجویان پیشرفته مقطع کارشناسی. هر فصل با تمرین‌هایی همراه است که بسیاری از آنها نکاتی را ارائه می‌کنند، در حالی که یادداشت‌های کتاب‌شناختی به انتشارات اصلی و کارهای مرتبط اشاره می‌کنند.

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.