Extending planar graph algorithms to K₃,3-free graphs

DOI10.1016/0890-5401(90)90031-CMaRDI QIDQ582121zbMATH OpenFDO

Authors Samir Khuller

Publication date 1990

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(90)90031-C

zbMATH Keywords

CRCW PRAMdepth first searchgraph coloringmaximal independentparallel algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (including graph drawing) in computer science (68R10)

Review text

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).

Recommendations

• scientific article; zbMATH DE number 4090822
• scientific article; zbMATH DE number 1769310
• Efficient Approximation Schemes for Maximization Problems onK3,3-free orK5-free Graphs
• Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs
• 5-coloring \(K_{3,k}\)-minor-free graphs

Cites work

• A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
• A note on primitive skew curves
• A random NC algorithm for depth first search
• An approach to the subgraph homeomorphism problem
• Dividing a Graph into Triconnected Components
• Efficient Planarity Testing
• Every planar map is four colorable. I: Discharging
• Finding small simple cycle separators for 2-connected planar graphs
• scientific article; zbMATH DE number 3887060 (Why is no real title available?)
• scientific article; zbMATH DE number 3729461 (Why is no real title available?)
• NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
• Parallel Algorithms for Depth-First Searches I. Planar Graphs

Cited in

(8)

• A parallel algorithm for finding a triconnected component separator with an application
• Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.
• scientific article; zbMATH DE number 4090822 (Why is no real title available?)
• scientific article; zbMATH DE number 4104996 (Why is no real title available?)
• Searching forK_3,3in linear time
• Efficient Approximation Schemes for Maximization Problems onK3,3-free orK5-free Graphs
• The Even-Path problem in directed single-crossing-minor-free graphs
• Parallel complexity of depth-first-search and maximal path in restricted graph classes

This page was built for publication: Extending planar graph algorithms to \(K_{3,3}\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q582121)