An improved algorithm for finding maximum outerplanar subgraphs

DOI10.1016/J.DAM.2023.08.009arXiv2306.05588OpenAlexW4387149517MaRDI QIDQ6184327

Hemanshu Kaul, Bahareh Kudarzi, Gruia Călinescu

Publication date: 24 January 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We study the NP-complete Maximum Outerplanar Subgraph problem. The previous best known approximation ratio for this problem is 2/3. We propose a new approximation algorithm which improves the ratio to 7/10.

Full work available at URL: https://arxiv.org/abs/2306.05588

zbMATH Keywords

approximation algorithmmatroid parityouterplanar graphmaximum subgraph

Mathematics Subject Classification ID

Numerical analysis (65-XX) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching theory
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Multicommodity flows in planar graphs
• Fast detection and display of symmetry in outerplanar graphs
• Characterizations of outerplanar graphs
• A new approximation algorithm for finding heavy planar subgraphs
• On the graphic matroid parity problem
• The sizes of maximal planar, outerplanar, and bipartite planar subgraphs
• Outerplanar partitions of planar graphs
• Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
• Heuristics for the maximum outerplanar subgraph problem
• Planarizing Graphs - A Survey and Annotated Bibliography
• Algebraic Algorithms for Linear Matroid Parity Problems
• Finding Triangles for Maximum Planar Subgraphs
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• Edge partition of planar sraphs into two outerplanar graphs
• A Better Approximation Algorithm for Finding Planar Subgraphs
• Approximation algorithms for NP-complete problems on planar graphs
• A GRASP for graph planarization
• The approximation of maximum subgraph problems
• A simulated annealing algorithm for the maximum planar subgraph problem
• Approximating the Minimum Equivalent Digraph
• Augmenting Outerplanar Graphs
• A Weighted Linear Matroid Parity Algorithm
• Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems
• Node-and edge-deletion NP-complete problems
• Embedding k-Outerplanar Graphs into l1

This page was built for publication: An improved algorithm for finding maximum outerplanar subgraphs