Extending planar graph algorithms to \(K_{3,3}\)-free graphs (Q582121)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Extending planar graph algorithms to \(K_{3,3}\)-free graphs |
scientific article |
Statements
Extending planar graph algorithms to \(K_{3,3}\)-free graphs (English)
0 references
1990
0 references
For several problems, restricting attention to special classes of graphs has yielded better algorithms. In particular, restricting to planar graphs yields efficient parallel algorithms for several graph problems. We extend these algorithms to \(K_{3,3}\)-free graphs, showing that the restriction of planarity is not important. The three problems dealt with are: graph coloring, depth first search, and maximal independent sets. As a corollary we show that \(K_{3,3}\)-free are five colorable (this bound is tight).
0 references
CRCW PRAM
0 references
parallel algorithms
0 references
graph coloring
0 references
depth first search
0 references
maximal independent
0 references
0 references