Analysis of heuristics for finding a maximum weight planar subgraph

DOI10.1016/0377-2217(85)90288-7zbMath0573.90093OpenAlexW2075838454WikidataQ56324168 ScholiaQ56324168MaRDI QIDQ1062924

Les R. Foulds, Alan M. Frieze, Martin Dyer

Publication date: 1985

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(85)90288-7

zbMATH Keywords

edge-weighted graphworst case ratiofacilities locationpolynomial-time heuristicsmaximum weight planar subgraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Finding clique clusters with the highest betweenness centrality, Sequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzles, Non-planar core reduction of graphs, Limits of Greedy Approximation Algorithms for the Maximum Planar Subgraph Problem, Heuristic methods and applications: A categorized survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel concepts in graph theory
• Facilities Layout Adjacency Determination: An Experimental Comparison of Three Graph Theoretic Heuristics
• Efficient Planarity Testing
• Hospital Layout as a Quadratic Assignment Problem
• An Analysis of the Greedy Heuristic for Independence Systems