Worst case analysis of a greedy algorithm for graph thickness

DOI10.1016/S0020-0190(02)00432-5MaRDI QIDQ1007554zbMATH OpenOpenAlexFDO

Authors Sinichiro Kawano, Koichi Yamazaki

Publication date 23 March 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(02)00432-5

zbMATH Keywords

graph algorithmsgraph thicknessgreedy algorithmmaximum planar subgraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Analysis of greedy algorithms on graphs with bounded degrees
• scientific article; zbMATH DE number 4116586
• Worst case analysis of a graph coloring algorithm
• Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
• The worst-case analysis of the Garey-Johnson algorithm
• scientific article; zbMATH DE number 1670532
• On the typical case complexity of graph optimization
• Worst-case analysis of greedy algorithms for the unbounded knapsack, subset-sum and partition problems
• scientific article; zbMATH DE number 3854439

Cites work

• Determining the thickness of graphs is NP-hard
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• Planarizing graphs---a survey and annotated bibliography
• The thickness of graphs: A survey

Cited in

(3)

• Worst case analysis of a graph coloring algorithm
• A simulated annealing algorithm for determining the thickness of a graph
• Linear programming and the worst-case analysis of greedy algorithms on cubic graphs

This page was built for publication: Worst case analysis of a greedy algorithm for graph thickness

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