A new approximation algorithm for finding heavy planar subgraphs

DOI10.1007/S00453-002-1020-3MaRDI QIDQ1400892zbMATH OpenOpenAlexFDO

Authors Gruia Calinescu, Cristina G. Fernandes, Howard Karloff, Alex Zelikovsky

Publication date 17 August 2003

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-002-1020-3

zbMATH Keywords

Approximation algorithmPerformance ratioWeighted planar graph

Mathematics Subject Classification ID

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

Recommendations

• A Better Approximation Algorithm for Finding Planar Subgraphs
• scientific article; zbMATH DE number 871895
• Two new approximation algorithms for the maximum planar subgraph problem
• Analysis of heuristics for finding a maximum weight planar subgraph
• scientific article; zbMATH DE number 2084267
• A linear time algorithm for finding maximal planar subgraphs
• A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
• Exact algorithms for the maximum planar subgraph problem: new models and experiments
• A note on the practicality of maximal planar subgraph algorithms
• Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems

Cited in

(11)

• On the \(k\)-restricted structure ratio in planar and outerplanar graphs
• An improved algorithm for finding maximum outerplanar subgraphs
• Finding large planar subgraphs and large subgraphs of a given genus
• Finding triangles for maximum planar subgraphs
• A \((1/2+1/60)\)-approximation algorithm for maximum weight series-parallel subgraph
• Heuristics for the maximum outerplanar subgraph problem
• A note on the maximum weight planar subgraph problem
• scientific article; zbMATH DE number 7559128 (Why is no real title available?)
• Maximum series-parallel subgraph
• scientific article; zbMATH DE number 871895 (Why is no real title available?)
• Analysis of heuristics for finding a maximum weight planar subgraph

This page was built for publication: A new approximation algorithm for finding heavy planar subgraphs

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