Computational Discrete Mathematics: Advanced Lectures (Lecture Notes in Computer Science, 2122)

✍ Scribed by Helmut Alt (editor)

• Publisher: Springer
• Year: 2001
• Tongue: English
• Leaves: 180
• Category: Library

✦ Synopsis

This book is based on a graduate education program on computational discrete mathematics run for several years in Berlin, Germany, as a joint effort of theoretical computer scientists and mathematicians in order to support doctoral students and advanced ongoing education in the field of discrete mathematics and algorithmics.
The 12 selected lectures by leading researchers presented in this book provide recent research results and advanced topics in a coherent and consolidated way. Among the areas covered are combinatorics, graph theory, coding theory, discrete and computational geometry, optimization, and algorithmic aspects of algebra.

✦ Table of Contents

Computational Discrete Mathematics
Preface
Table of Contents
Lattice Paths and Determinants
Four Problems
The Lemma of Gessel and Viennot
A Graphical Approach to Determinants
Solving the Problems
References
The Nearest Neighbor
The Problem
The Voronoi-Diagram Approach
The Curse of Dimensionality
Approximate Solutions
Brute Force Revisited
References
Explicit and Implicit Enforcing - Randomized Optimization
Introduction
Smallest Enclosing Ball
Boundary (Explicit) Enforcing
Implicit Enforcing
Bibliographical Remarks and Discussion
An Estimate for Cycle Numbers
References
Codes over Z4
Introduction
Coding Theory
Galois Rings
Kerdock and Preparata Codes over $Z_4$
Conclusions
References
Degree Bounds for Long Paths and Cycles in k-Connected Graphs
References
Data Structures for Boolean Functions
Introduction
Data Structures for Boolean Functions
OBDDs -- Ordered Binary Decision Diagrams
Definitions
Operations on and with OBDDs
Efficient Synthesis of OBDDs
Construction of OBDDs: Symbolic Simulation
Influence of the Variable Order on the OBDD Size
Paradigmatic Applications of OBDDs in Formal Verification
Verification of Combinatorial Circuits
Formal Verification of Sequential Systems
Symbolic Model Checking
Optimization of Variable Ordering for OBDDs
Static Techniques
Dynamic Techniques
Variants of the BDD Data Structure
Ordered Functional Decision Diagrams (OFDDs)
Transformed Binary Decision Diagrams (TBDDs)
Parity-OBDDs ($oplus $-OBDDs)
Establishing a WWW Portal for BDD Research
References
Scheduling under Uncertainty: Bounding the Makespan Distribution
Uncertainty in Scheduling
The Complexityhfill penalty -@M of Evaluating the Makespan Distribution
A General Bounding Principle
Bounding with Series-Parallel Networks
Specific Bounds
The Bound of Dodin
The Bounds of Spelde
Computational Experience
References
Random Graphs, Random Triangle-Free Graphs, and Random Partial Orders
Introduction
Random Graphs
General Properties of a Random Graph
Clique Number and Chromatic Number of a Random Graph
Random Triangle--Free Graphs
Random Triangle-Free Graphs Are Bipartite
Evolution of Random Graphs
Evolution of Random Triangle-Free Graphs
Random Maximal Triangle-Free Graphs
Random Partial Orders
Random Partial Orders Have Height Three
Evolution of Random Partial Orders
References
Division-Free Algorithms for the Determinant and the Pfaffian: Algebraic and Combinatorial Approaches
Introduction
Algorithms for the Determinant
Alternate Expressions for the Determinant
Cycle Decompositions
Clow Sequences
Dynamic Programming According to Length
Adding a Vertex at a Time: Combinatorial Approach
The Characteristic Polynomial
Adding a Vertex at a Time: Algebraic Approach
Who Invented the Incremental Algorithm?
The Pfaffian
Alternating Cycle Decompositions
Alternating Clow Sequences
Incremental Algorithms for the Pfaffian
Open Questions
The Pfaffian-Characteristic Polynomial:hfill penalty -@M Algebraic Interpretation
Complexity
Alternative Algorithms
References
Check Character Systems and Anti-symmetric Mappings
Introduction
First Definitions and Historical Remarks
Error Types to Be Detected
Systems over Groups
First Examples
Anti-symmetric Mappings
The Abelian Case
Further Examples
Existence Theorems
Anti-automorphisms and Good Automorphisms
Equivalence of Check Digit Systems
Weak Equivalence
Automorphism Equivalence and Strong Equivalence
Generalization to Quasigroups
Solution of the Exercise
References
Algorithms in Pure Mathematics
Introduction
Galois Groups
Groups
References
Coloring Hamming Graphs, Optimal Binary Codes, and the 0/1-Borsuk Problem in Low Dimensions
Introduction
The 0/1-Borsuk Problem
Reformulation as a Coloring Problem
Coloring Hamming Graphs
Some Coding Theory Bounds Are Used
A Hamming Code Is Used
Coloring Hamming Graphs, III
The 0/1-Borsuk Problem in Low Dimensions
Coloring Hamming Graphs, III
The Hamming Graphs relax mathversion {bold}{$H_{d,2}$} -- Stefan Hougardy
A Lower Bound for Small Diameter -- Jon McCammond
An Upper Bound for Large Diameter -- Noga Alon
References
Author Index