PPT Slide

• Similar phenomenon for graph coloring.

  • random graphs
  • 3-coloring; threshold around 4.6 (connectivity)
    (Cheeseman et al. 1991)
    

• Critically-constrained --- Practical relevance

  • Airline fleet scheduling (Nemhauser 1994)
  • VLSI design (Agrawal 1991)
  • Traveling Salesperson Problem (Gent and Walsh 1995)

See also Hogg, Huberman, and Williams 1996; Crawford and Auton 1993; Frost and Dechter 1994; Larrabee and Tsuji 1993; Schrag and Crawford 1996; Smith and Grant 1994; Smith and Dyer 1996; and more!

Previous slide

Next slide

Back to first slide

View graphic version