مسائل مسیر در شبکه‌ها ۲۰۲۲
Path Problems in Networks 2022

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

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

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

فهرست مطالب: کوتاه‌ترین مسیر کلاسیک / مسئله‌ی مسیر جبری / خواص و محاسبه‌ی حل‌ها / کاربردها / حوزه‌های مرتبط / فهرست نیم‌حلقه‌ها و کاربردها

The algebraic path problem is a generalization of the shortest path problem in graphs. Various instances of this abstract problem have appeared in the literature, and similar solutions have been independently discovered and rediscovered. The repeated appearance of a problem is evidence of its relevance. This book aims to help current and future researchers add this powerful tool to their arsenal, so that they can easily identify and use it in their own work. Path problems in networks can be conceptually divided into two parts: A distillation of the extensive theory behind the algebraic path problem, and an exposition of a broad range of applications. First of all, the shortest path problem is presented so as to fix terminology and concepts: existence and uniqueness of solutions, robustness to parameter changes, and centralized and distributed computation algorithms. Then, these concepts are generalized to the algebraic context of semirings. Methods for creating new semirings, useful for modeling new problems, are provided. A large part of the book is then devoted to numerous applications of the algebraic path problem, ranging from mobile network routing to BGP routing to social networks. These applications show what kind of problems can be modeled as algebraic path problems; they also serve as examples on how to go about modeling new problems. This monograph will be useful to network researchers, engineers, and graduate students. It can be used either as an introduction to the topic, or as a quick reference to the theoretical facts, algorithms, and application examples. The theoretical background assumed for the reader is that of a graduate or advanced undergraduate student in computer science or engineering. Some familiarity with algebra and algorithms is helpful, but not necessary. Algebra, in particular, is used as a convenient and concise language to describe problems that are essentially combinatorial. Table of Contents: Classical Shortest Path / The Algebraic Path Problem / Properties and Computation of Solutions / Applications / Related Areas / List of Semirings and Applications