Heuristics for the maximum outerplanar subgraph problem

DOI10.1007/S10732-005-6999-6MaRDI QIDQ2573002zbMATH OpenOpenAlexFDO

Authors Timo Poranen

Publication date 7 November 2005

Published in Journal of Heuristics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10732-005-6999-6

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A simulated annealing algorithm for the maximum planar subgraph problem
• Publication:4886062
• Analysis of heuristics for finding a maximum weight planar subgraph
• A Better Approximation Algorithm for Finding Planar Subgraphs
• Branch-and-bound techniques for the maximum planar subgraph problem^∗

Cites work

• scientific article; zbMATH DE number 2084287 (Why is no real title available?)
• scientific article; zbMATH DE number 4048925 (Why is no real title available?)
• scientific article; zbMATH DE number 3668651 (Why is no real title available?)
• scientific article; zbMATH DE number 3692662 (Why is no real title available?)
• scientific article; zbMATH DE number 3614802 (Why is no real title available?)
• scientific article; zbMATH DE number 3628989 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305401 (Why is no real title available?)
• scientific article; zbMATH DE number 1016966 (Why is no real title available?)
• scientific article; zbMATH DE number 1488569 (Why is no real title available?)
• scientific article; zbMATH DE number 1522938 (Why is no real title available?)
• scientific article; zbMATH DE number 910888 (Why is no real title available?)
• scientific article; zbMATH DE number 3334023 (Why is no real title available?)
• A Better Approximation Algorithm for Finding Planar Subgraphs
• A GRASP for graph planarization
• A new approximation algorithm for finding heavy planar subgraphs
• A new planarity test
• A simulated annealing algorithm for the maximum planar subgraph problem
• An analysis of heuristics for graph planarization
• An efficient graph planarization two‐phase heuristic
• Augmenting Outerplanar Graphs
• Efficient Planarity Testing
• Fast detection and display of symmetry in outerplanar graphs
• Fully dynamic planarity testing with applications
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Node-and edge-deletion NP-complete problems
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Optimization by simulated annealing
• Planarizing graphs---a survey and annotated bibliography
• The sizes of maximal planar, outerplanar, and bipartite planar subgraphs
• The thickness of graphs: A survey
• Time-Dependent Statistics of the Ising Model

Cited in

(4)

• An algorithmic metatheorem for directed treewidth
• A simulated annealing algorithm for the maximum planar subgraph problem
• An improved algorithm for finding maximum outerplanar subgraphs
• Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size

Describes a project that uses

Uses Software

• DIMACS
• LEDA

This page was built for publication: Heuristics for the maximum outerplanar subgraph problem

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