Now on ScienceBlogs: And so, driven on ceaselessly toward new shores
Finding the fun in good math; Shredding bad math and squashing the crackpots who espouse it.
Mark Chu-Carroll (aka MarkCC) is a PhD Computer Scientist, who works for Google as a Software Engineer. My professional interests center on programming languages and tools, and how to improve the languages and tools that are used for building complex software systems.
Category: Graph Theory
In my last post on game theory, I said that you could find an optimal probabilistic grand strategy for any two-player, simultaneous move, zero-sum game. It's done through something called linear programming. But linear programming is useful for a...
Posted by Mark C. Chu-Carroll at 2:28 PM • 25 Comments •
Category: Graph Theory
As promised, today I'm going to talk about how to compute the strongly connected components of a directed graph. I'm going to go through one method, called Kosaraju's algorithm, which is the easiest to understand. It's possible to do...
Posted by Mark C. Chu-Carroll at 9:09 PM • 20 Comments •
Category: Networks
Colored Petri Nets The big step in Petri nets - the one that really takes them from a theoretical toy to a serious tool used by protocol developers - is the extension to colored Petri nets (CPNs). Calling them "colored"...
Posted by Mark C. Chu-Carroll at 9:03 AM • 8 Comments •
Category: Networks
There's one variant of Petri nets, called counted Petri nets, which I'm fond of for personal reasons. As Petri net variants go, it's a sort of sloppy but simple one, but as I said, I'm fond of it. As...
Posted by Mark C. Chu-Carroll at 9:12 PM • 9 Comments •
Category: Graph Theory
Among many of the fascinating things that we computer scientists do with graphs is use them as a visual representation of computing devices. There are many subtle problems that can come up in all sorts of contexts where being...
Posted by Mark C. Chu-Carroll at 8:11 PM • 12 Comments •
Category: Graph Theory
Yet another example of how graphs can be used as models to solve real problems comes from the world of project management. I tend to cringe at anything that involves management; as a former IBMer, I've dealt with my...
Posted by Mark C. Chu-Carroll at 12:28 PM • 5 Comments •
Category: Graph Theory
There's a kind of graph which is very commonly used by people like me for analysis applications, called a lattice. A lattice is a graph with special properties that make it extremely useful for representing information in an analysis...
Posted by Mark C. Chu-Carroll at 9:09 PM • 12 Comments •
Category: Graph Theory
Last time, I showed a way of using a graph to model a particular kind of puzzle via a search graph. Games and puzzles provide a lot of examples of how we can use graphs to model problems. Another...
Posted by Mark C. Chu-Carroll at 11:58 AM • 11 Comments •
Category: Graph Theory
As I've mentioned before, the real use of graphs is as models. Many real problems can be described using graphs as models - that is, to translate the problem into a graph, solve some problem on the graph, and...
Posted by Mark C. Chu-Carroll at 9:00 AM • 8 Comments •
Category: Graph Theory
Suppose you've got a huge graph - millions of nodes. And you know that it's not connected - so the graph actually consists of some number of pieces (called the connected components of the graph). And there are constantly...
Posted by Mark C. Chu-Carroll at 11:40 AM • 12 Comments •
