[HN Gopher] Graph Coloring Methods
___________________________________________________________________
Graph Coloring Methods
Author : silasdb
Score : 59 points
Date : 2024-09-21 09:41 UTC (4 days ago)
(HTM) web link (graphcoloringmethods.com)
(TXT) w3m dump (graphcoloringmethods.com)
| n4r9 wrote:
| This looks like a nice book. I took courses in graph theory and
| ramsey theory at university many years ago. Reading the first
| couple of pages of the first chapter, it's pitched at a good
| level for me to jump back into things.
|
| Users might find this paragraph from the Preface helpful:
|
| > This book is about graph coloring, one of the most popular and
| widely-studied areas of discrete mathematics. The intended reader
| is a graduate student or early career researcher, although it
| should be useful for readers who are both less and more
| experienced. The reader may find it useful to have taken a
| 1-semester course in graph theory, but this is not strictly
| necessary. My goal as the author is to help you understand,
| internalize, and add to (if you like) central results in many
| areas of graph coloring.
|
| The first chapter also states:
|
| > In this book we focus on the existence of colorings, rather
| than on algorithms to produce them
|
| Does anyone know of resources for learning or implementing
| algorithms for graph colouring?
| siegelzero wrote:
| I can recommend the book Guide to Graph Colouring: Algorithms
| and Applications by Lewis. It covers techniques including some
| state of the art methods for getting good but not provably
| optimal colorings. It discusses in depth local search and
| hybrid evolutionary algorithms, which tend to be the best
| performing on academic benchmarks (DIMACS graphs and large
| random graphs).
| datadrivenangel wrote:
| "More precisely, it is NP-hard1. So it is unlikely that we will
| find an efficient algorithm to optimally solve the coloring
| problem on an arbitrary input graph. This fundamental hardness
| result casts a long shadow across the landscape of graph
| coloring."
| HarHarVeryFunny wrote:
| Yes, but in practice heuristic approaches can work well, even
| if there are no guarantees of optimality. See for example my
| response about a simple "most constrained first" heuristic.
| qwertox wrote:
| I was expecting some pretty, colored graphs, but the book is in
| black and white.
|
| From Wikipedia [0]:
|
| _In graph theory, graph coloring is a special case of graph
| labeling; it is an assignment of labels traditionally called
| "colors" to elements of a graph subject to certain constraints._
|
| [0] https://en.wikipedia.org/wiki/Graph_coloring
| madcaptenor wrote:
| I'm surprised too, especially given that this seems primarily
| intended as a book to read online so the extra printing costs
| for color wouldn't be an issue. I imagine there are some places
| in the book where there are large numbers of "colors" and so it
| wouldn't be helpful to show them as actual colors - but surely
| there are some places where actual colors would be useful.
| motohagiography wrote:
| it makes more sense in the applications, asking AI, you get
| examples like how to schedule exams so that no student has a
| conflict, scheduling flight crews, radio frequency assignment
| to avoid overlap. e.g. "By representing flights as vertices and
| connecting edges between flights that share crew members, a
| coloring algorithm assigns crews to flights to minimize
| conflicts"
| throwaway290 wrote:
| If you think you must ask AI for this, wait till you learn
| Wikipedia article you replied on says just that but with more
| sourced detail and less possibility for accidental falsehood
| motohagiography wrote:
| the falsehoods on wikipedia are usually purposeful
| deceptions so I tend not to bother with it as a go-to. net-
| net AI has about the same level of accuracy and lacks the
| actual mendacity.
|
| almost none of us are going to move any discipline forward,
| let alone discover new math, but as part of the long tail
| of people who could benefit from recognizing classes of
| problems with solutions in the domain of graph colouring,
| AI is sufficient for most purposes.
|
| sorry that nobody appreciates your effort though.
| generationP wrote:
| Lots of academic authors have decided color is a gimmick (color
| printing is expensive and not clear how long-lived; grayscale
| printing kills yellow and light-green lines; then there is
| colorblindness). Certainly I agree that _load-bearing_ color is
| to be avoided, and I do so in my own writing.
| HarHarVeryFunny wrote:
| With so many methods, it'd be interesting to get some feel for
| what percentage of random graphs, or graphs of a particular type
| perhaps, can be optimally colored using each technique.
|
| The subject reminds me of a YACC-like parser generator I wrote
| back in the early 80's... Using graph coloring to compress the
| parser tables.
|
| My generator was more general than YACC, accepting LR(1) grammars
| rather than LALR(1) ones, a feat which was considered impractical
| at that time (said Aho & Ullman's "dragon book"). Certainly a
| canonical Knuth parser would be huge, but what made it possible
| was to use an at the time obscure state-combining technique
| invented by Prof. Pager. However, the resulting parse tables (2-D
| array, indexed by parser state and current symbol) were still
| huge, although sparse. One solution was to represent the tables
| as linked lists, but I wanted to instead compress them to keep
| the speed of array access.
|
| The solution I used was to convert the sparse 2-D array to a
| graph, color the graph, then convert it back to a compressed
| array where non-conflicting (sparse) rows and columns had been
| combined.
|
| The idea was to:
|
| 1) Convert each row of the 2-D array to a graph node, and connect
| that node to all other nodes who's corresponding row had a
| conflicting column entry.
|
| 2) Color the resulting graph (i.e. assign colors to nodes, such
| that connected nodes have different colors, using fewest possible
| colors). The simple but effective coloring heuristic I used was
| just to assign colors to the "hardest" (i.e. most constrained)
| nodes first - those with the most connections.
|
| 3) Convert the colored graph back to a 2-D array by combining all
| rows (nodes) of the same color, which by construction meant rows
| not having any conflicting entries would be combined, and the
| array would be compressed in accordance to how few colors had
| been used.
|
| 4) Repeat steps 1-3 for the columns.
|
| What I liked about this algorithm was that any future research
| into optimal graph coloring could be applied to it to achieve
| better compression, although this was just a side project and I
| never did revisit it.
|
| The resulting parsers (I implemented both K&R C and Modula-2)
| were indeed stupid fast due to just using array access. I don't
| remember how big the compressed tables were for these languages,
| but they happily ran on the Acorn 32016 2nd processor I was using
| for development (I did this while working for Acorn Computers).
|
| Incidentally, the "do the hardest/most-constrained bits first" is
| a useful heuristic for many problems - e.g. I remember also using
| it so solve the "knight's tour" chessboard problem (have a knight
| visit each square on a chessboard exactly once).
| j2kun wrote:
| Is there any good reference (in this book or another) that gives
| a sense of what coloring methods work well for various practical
| problems? Do they still use graph coloring for register
| allocation--and if so, which method is used?
|
| I have heard of some people using the "degree saturation" method
| (DSATUR: https://en.wikipedia.org/wiki/DSatur), but a systematic
| review would be really interesting.
| generationP wrote:
| I'm seeing some influence of [Diestel](https://diestel-graph-
| theory.com/) at least on the layout of the text.
___________________________________________________________________
(page generated 2024-09-25 23:01 UTC)