1st Edition

Combinatorial Algorithms Generation, Enumeration, and Search

    344 Pages
    by CRC Press

    342 Pages
    by CRC Press

    This textbook thoroughly outlines combinatorial algorithms for generation, enumeration, and search. Topics include backtracking and heuristic search methods applied to various combinatorial structures, such as:

  • Combinations
  • Permutations
  • Graphs
  • Designs

  • Many classical areas are covered as well as new research topics not included in most existing texts, such as:
  • Group algorithms
  • Graph isomorphism
  • Hill-climbing
  • Heuristic search algorithms

  • This work serves as an exceptional textbook for a modern course in combinatorial algorithms, providing a unified and focused collection of recent topics of interest in the area. The authors, synthesizing material that can only be found scattered through many different sources, introduce the most important combinatorial algorithmic techniques - thus creating an accessible, comprehensive text that students of mathematics, electrical engineering, and computer science can understand without needing a prior course on combinatorics.
  • Structures and Algorithms
    What are Combinatorial Algorithms?
    What are Combinatorial Structures?
    What are Combinatorial Problems?
    Analysis of Algorithms
    Complexity Classes
    Data Structures
    Algorithm Design Techniques
    Generating Elementary Combinatorial Objects
    Combinatorial Generation
    k-Element Subsets
    More Topics in Combinatorial Generation
    Integer Partitions
    Set Partitions, Bell and Stirling Numbers
    Labeled Trees
    Catalan Families
    Backtracking Algorithms
    A General Backtrack Algorithm
    Generating All Cliques
    Estimating the Size of a Backtrack Tree
    Exact Cover
    Bounding Functions
    Heuristic Search
    Introduction to Heuristic Algorithms
    Design Strategies for Heuristic Algorithms
    A Steepest-Ascent Algorithm for Uniform Graph Partition
    A Hill-Climbing Algorithm for Steiner Triple Systems
    Two Heuristic Algorithms for the Knapsack Problem
    A Genetic Algorithm for the Traveling Salesman Problem
    Groups and Symmetry
    Permutation Groups
    Orbits of Subsets
    Coset Representatives
    Orbits of k-tuples
    Generating Objects Having Automorphisms
    Computing Isomorphism
    Computing Certificates
    Isomorphism of Other Structures
    Basis Reduction
    Theoretical Development
    A Reduced Basis Algorithm
    Solving Systems of Integer Equations
    The Merkle-Hellman Knapsack System
    Algorithm Index
    Problem Index


    Kreher, Donald L.; Stinson, Douglas R.