Sparsity: Graphs, Structures, and Algorithms

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

این مطالعه ساختارهای پراکنده کاربردهایی در زمینه‌های متنوعی مانند نظریه گراف الگوریتمی، پیچیدگی الگوریتم‌ها، تست ویژگی، پیچیدگی توصیفی و ریاضی یافت. منطق (حفظ هممورفیسم، قابلیت انتقال پارامتر ثابت و مشکلات رضایت از محدودیت). لازم به ذکر است که این رویکرد علیرغم عمومیت خود منجر به الگوریتم های خطی (و تقریباً خطی) می شود.

Jaroslav Nešetřil استاد دانشگاه چارلز پراگ است. پاتریس اوسونا دی مندز، محقق CNRS و EHESS، پاریس است.

این کتاب مربوط به مطالب ارائه شده توسط اولین نویسنده در ICM 2010 است.

This is the first book devoted to the systematic study of sparse graphs and sparse finite structures. Although the notion of sparsity appears in various contexts and is a typical example of a hard to define notion, the authors devised an unifying classification of general classes of structures. This approach is very robust and it has many remarkable properties. For example the classification is expressible in many different ways involving most extremal combinatorial invariants.

This study of sparse structures found applications in such diverse areas as algorithmic graph theory, complexity of algorithms, property testing, descriptive complexity and mathematical logic (homomorphism preservation,fixed parameter tractability and constraint satisfaction problems). It should be stressed that despite of its generality this approach leads to linear (and nearly linear) algorithms.

Jaroslav Nešetřil is a professor at Charles University, Prague; Patrice Ossona de Mendez is a CNRS researcher et EHESS, Paris.

This book is related to the material presented by the first author at ICM 2010.