Discrete Applied Math by Bahareh Kudarzi: An Improved Algorithm for Finding Maximum Outerplanar Subgraphs

Speaker:

Bahareh Kudarzi, Illinois Institute of Technology

Title: An Improved Algorithm for Finding Maximum Outerplanar Subgraphs

Abstract: 

We study the NP-complete problem of Maximum Outerplanar Subgraph. The
problem asks for a polynomial-time algorithm for finding an
outerplanar subgraph of a given graph with as large a number of edges
as possible. Outerplanar graphs have been investigated in-depth for
their applications and theoretical properties, especially as most
problems which are NP-hard on arbitrary graphs become polynomial on
outerplanar graphs. In this talk, we will introduce a novel
approximation algorithm, improving the previous best-known
approximation ratio of $2/3$ to $7/10$ for this problem.  The proposed
method combines greedy techniques with matching methods presenting a
fresh approach to the problem. Furthermore, the analysis provided is
elementary and robust, possibly applicable in broader contexts.
This is joint work with  Gruia Calinescu, Hemanshu Kaul

 

Discrete Applied Math Seminar

Request Zoom Link