Connections in Combinatorial Optimization

1. Auflage 2018
ISBN: 978-0-19-920527-1
Verlag: Oxford University Press (UK)

Buch, Englisch, Band 38, 664 Seiten, Format (B × H): 161 mm x 240 mm, Gewicht: 1151 g

Reihe: Oxford Lecture Series in Mathematics and Its Applications

Graph connectivities and submodular functions are two widely applied and fast developing fields of combinatorial optimization. This book not only includes the most recent results, but also highlights several surprising connections between diverse topics within combinatorial optimization. It offers a unified treatment of developments in the concepts and algorithmic methods of the area, starting from basic results on graphs, matroids and polyhedral combinatorics, through the advanced topics of connectivity issues of graphs and networks, to the abstract theory and applications of submodular optimization. Difficult theorems and algorithms are made accessible to graduate students in mathematics, computer science, operations research, informatics and communication.

The book is not only a rich source of elegant material for an advanced course in combinatorial optimization, but it also serves as a reference for established researchers by providing efficient tools for applied areas like infocommunication, electric networks and structural rigidity.

Zielgruppe

Graduates and researchers in mathematics, computer science, informatics, and communication that rely on methods of combinatorial optimization.

Autoren/Hrsg.

Frank, András

Fachgebiete

• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
• Technische Wissenschaften Technik Allgemein Mathematik für Ingenieure
• Mathematik | Informatik Mathematik Operations Research Graphentheorie
• Mathematik | Informatik EDV | Informatik Computerkommunikation & -vernetzung

Inhaltsverzeichnis

Preface
PART I - Basic Combinatorial Optimization
1: Elements of graphs and hypergraphs
2: Connectivity, paths, and matchings
3: Elements of network optimization
4: Elements of polyhedral combinatorics
5: Elements of matroid theory
PART II - Higher-Order Connections
6: Efficient algorithms for flows and cuts
7: Structure and representations of cuts
8: The splitting off operation and constructive characterizations
9: Orientations of graphs and hypergraphs
10: Trees and arborescences: packing and covering
11: Preserving and improving connections
PART III - Semimodular Optimization
12: Setting the stage: aspects and approaches
13: Matroid optimization
14: Generalized polymatroids
15: Relaxing semimodularity
16: Submodular flows
17: Covering supermodular functions by digraphs
Solutions to selected problems
Bibliography
Index

Über Autor(innen)

András Frank is the founder and head of the MTA-ELTE Egerváry Research Group (EGRES) at Eötvös University. He was head of the Department of Operations Research at Eötvös University between 1995 and 2009. In 2002, he was awarded the Tibor Szele Prize by the János Bolyai Mathematical Society, and in 2009, the Cultural Ministry of Hungary awarded him the Szent-Gyorgyi Albert Prize.