Handbook of Graph Theory, Combinatorial Optimization, and Algorithms

ISBN-13: 9781584885955 / Angielski / Twarda / 2015 / 1226 str.

Krishnaiyan Thulasiraman;Tako Nishizeki;Guoliang Xue

Opis

The fusion between graph theory and combinatorial optimization has led to theoretically profound and practically useful algorithms, yet there is no book that currently covers both areas together. Handbook of Graph Theory, Combinatorial Optimization, and Algorithms is the first to present a unified, comprehensive treatment of both graph theory and combinatorial optimization. Divided into 11 cohesive sections, the handbook s 44 chapters focus on graph theory, combinatorial optimization, and algorithmic issues. The book provides readers with the algorithmic and theoretical foundations to:

• Understand phenomena as shaped by their graph structures
• Develop needed algorithmic and optimization tools for the study of graph structures
• Design and plan graph structures that lead to certain desirable behavior

With contributions from more than 40 worldwide experts, this handbook equips readers with the necessary techniques and tools to solve problems in a variety of applications. Readers gain exposure to the theoretical and algorithmic foundations of a wide range of topics in graph theory and combinatorial optimization, enabling them to identify (and hence solve) problems encountered in diverse disciplines, such as electrical, communication, computer, social, transportation, biological, and other networks."

Since the 1970s, many engineering disciplines have relied extensively on graph theory as a primary tool for analysis and design. The Handbook of Graph Algorithms, Volume 1: Theory and Optimization provides comprehensive coverage of basic concepts and recent developments in the field. Focusing on design, proof of correctness, and complexity analysis, this volume presents a detailed discussion of algorithms that are useful in a variety of applications and provides an authoritative review of the current state of the art. Using figures to help illustrate the concepts, the book examines topics such as incremental algorithms and online algorithms that have yet to receive much attention but have great potential for future applications.

Spis treści

Basic Concepts and Algorithms. Flows in Networks. Algebraic Graph Theory. Structural Graph Theory. Planar Graphs. Interconnection Networks. Special Graphs. Partitioning. Matroids. Probabilistic Methods, Random Graph Models, and Randomized Algorithms. Coping with NP-Completeness.