Browse by Tags

Tagged Content List
  • Blog Post: Graph Colouring, Part Five

    I said last time that I was interested in finding colourings for graphs that have lots of fully connected subgraphs, aka "cliques". For instance, I'd like to find a four-colouring for this sixteen-node graph: Yuck. What a mess. What this graph is doing a bad job of conveying is that there are...
  • Blog Post: Graph Colouring, Part Four

    Let's give it a try. Can we colour South America with only four colours? Let's start by stating what all the edges are in the graph of South America: const int Brazil = 0; const int FrenchGuiana = 1; const int Suriname = 2; const int Guyana = 3; const int Venezuala = 4; const int Colombia = 5;...
  • Blog Post: Graph Colouring with Simple Backtracking, Part Three

    OK, we've got our basic data structures in place. Graph colouring is a very well-studied problem. It's known to be NP-complete for arbitrary graphs, so (assuming that P!=NP) we're not going to find an always-fast algorithm for colouring an arbitrary graph. However, for typical graphs that we encounter...
  • Blog Post: Graph Colouring With Simple Backtracking, Part Two

    Before I begin a quick note: congratulations and best wishes to David Johnson, currently the president of my alma mater, the University of Waterloo. The Queen has appointed him to be the next Governor General of Canada come this October. For those of you unfamiliar with the Canadian political structure...
  • Blog Post: Graph Colouring With Simple Backtracking, Part One

    As regular readers know, I'm interested in learning how to change my C# programming style to emphasize more concepts from functional programming, like use of immutable rather than mutable data structures and use of declarative control flow like LINQ queries instead of imperative control flow in the form...
Page 1 of 1 (5 items)