Back to Search Start Over

An Improved Algorithm for Finding Maximum Outerplanar Subgraphs

Authors :
Calinescu, Gruia
Kaul, Hemanshu
Kudarzi, Bahareh
Publication Year :
2023

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.

Subjects

Subjects :
Computer Science - Data Structures and Algorithms
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2306.05588
Document Type :
Working Paper

Tools

Authors Abstract Subjects Details