Heuristics for the maximum outerplanar subgraph problem

DOI10.1007/S10732-005-6999-6zbMATH Open1122.90416OpenAlexW2125652787MaRDI QIDQ2573002FDOQ2573002

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

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^∗

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)

Cites Work

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

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

Uses Software

• LEDA
• DIMACS

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)