Книга "Tree-based Graph Partitioning Constraint" рассматривает проблемы комбинаторики, основанные на разбиении графов, которые позволяют математически моделировать многие практические приложения, такие как планирование миссии и проблемы маршрутизации в логистике. Однако эти проблемы не основаны на одном и том же типе разбиения: обычно выделяют разбиения на циклы, пути или деревья. Кроме того, практические применения часто не ограничиваются теоретическими задачами, такими как задача о гамильтоновом пути или задачи о K-непересекающихся путях. Они обычно сочетают задачу разбиения графа с несколькими ограничениями, связанными с топологией узлов и дуг. Разнообразие подразумеваемых ограничений в реальных приложениях является практическим ограничением для решения таких задач методами, рассматривающими задачу разбиения графа независимо от каждого дополнительного ограничения. Эта книга фокусируется на задачах удовлетворения ограничений, связанных с задачами разбиения дерева, обогащенных несколькими дополнительными ограничениями, которые ограничивают возможную топологию разбиений. С одной стороны, эта книга фокусируется на структурных свойствах ограничений разбиения дерева. С другой стороны, она посвящена взаимодействию между задачей разбиения дерева и классическими ограничениями (например, отношениями предшествования или непересекаемости между узлами), связанными с практическими приложениями. Книга показывает, как глобально учитывать несколько ограничений в рамках одного единственного ограничения разбиения дерева. Еще один интересный аспект этой книги связан с реализацией такого ограничения. В контексте графических глобальных ограничений книга иллюстрирует, как полностью динамическое управление структурами данных делает время выполнения алгоритмов фильтрации независимым от плотности графа.
Электронная Книга «Tree-based Graph Partitioning Constraint» написана автором Xavier Lorca в году.
Минимальный возраст читателя: 0
Язык: Английский
ISBN: 9781118604472
Описание книги от Xavier Lorca
Combinatorial problems based on graph partitioning enable us to mathematically represent and model many practical applications. Mission planning and the routing problems occurring in logistics perfectly illustrate two such examples. Nevertheless, these problems are not based on the same partitioning pattern: generally, patterns like cycles, paths, or trees are distinguished. Moreover, the practical applications are often not limited to theoretical problems like the Hamiltonian path problem, or K-node disjoint path problems. Indeed, they usually combine the graph partitioning problem with several restrictions related to the topology of nodes and arcs. The diversity of implied constraints in real-life applications is a practical limit to the resolution of such problems by approaches considering the partitioning problem independently from each additional restriction. This book focuses on constraint satisfaction problems related to tree partitioning problems enriched by several additional constraints that restrict the possible partitions topology. On the one hand, this title focuses on the structural properties of tree partitioning constraints. On the other hand, it is dedicated to the interactions between the tree partitioning problem and classical restrictions (such as precedence relations or incomparability relations between nodes) involved in practical applications. Precisely, Tree-based Graph Partitioning Constraint shows how to globally take into account several restrictions within one single tree partitioning constraint. Another interesting aspect of this book is related to the implementation of such a constraint. In the context of graph-based global constraints, the book illustrates how a fully dynamic management of data structures makes the runtime of filtering algorithms independent of the graph density.
