arXiv Open Access 2019

The Densest k Subgraph Problem in b-Outerplanar Graphs

Sean Gonzales Theresa Migler

Lihat Sumber

Abstrak

We give an exact $O(nk^2)$ algorithm for finding the densest k subgraph in outerplanar graphs. We extend this to an exact $O(nk^2 8^b)$ algorithm for finding the densest k subgraph in b-outerplanar graphs. Finally, we hypothesize that Baker's PTAS technique will not work for the densest k subgraph problem in planar graphs.

Topik & Kata Kunci

cs.DS

Penulis (2)

Sean Gonzales

Theresa Migler

Format Sitasi

APA MLA BibTeX

Gonzales, S., Migler, T. (2019). The Densest k Subgraph Problem in b-Outerplanar Graphs. https://arxiv.org/abs/1907.03863

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2019
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓