Branch-and-bound techniques for the maximum planar subgraph problem∗

DOI10.1080/00207169408804320zbMath0842.68057OpenAlexW2015924510MaRDI QIDQ4844576

Robert J. Cimikowski

Publication date: 10 October 1995

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207169408804320

zbMATH Keywords

branch-and-bound algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

A simulated annealing algorithm for the maximum planar subgraph problem

Cites Work

• Unnamed Item
• On linear-time algorithms for five-coloring planar graphs
• A linear algorithm for embedding planar graphs using PQ-trees
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A batching method for coloring planar graphs
• An algorithm for finding a maximum weighted independent set in an arbitrary graph
• Facilities Layout Adjacency Determination: An Experimental Comparison of Three Graph Theoretic Heuristics
• Finding a Maximum Clique in an Arbitrary Graph
• Efficient Planarity Testing
• An Efficient Heuristic Procedure for Partitioning Graphs
• Finding a Maximum Independent Set
• An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem
• An efficient graph planarization two‐phase heuristic
• An analysis of heuristics for graph planarization

This page was built for publication: Branch-and-bound techniques for the maximum planar subgraph problem^∗