Worst case analysis of a greedy algorithm for graph thickness

✍ Scribed by Sinichiro Kawano; Koichi Yamazaki

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 208 KB
• Volume: 85
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(02)00432-5

✦ Synopsis

In this paper, we consider a greedy algorithm for thickness of graphs. The greedy algorithm we consider here takes a maximum planar subgraph away from the current graph in each iteration and repeats this process until the current graph has no edge. The greedy algorithm outputs the number of iterations which is an upper bound of thickness for an input graph G = (V , E). We show that the performance ratio of the greedy algorithm is (log |V |).