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




Online event


Bahareh Kudarzi, Illinois Institute of Technology

Title: An Improved Algorithm for Finding Maximum Outerplanar Subgraphs


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


Event Contact

Hemanshu Kaul
Co-Director, M.S. in Computational Decision Science and Operations Research (CDSOR) Associate Professor of Applied Mathematics

Getting to Campus