Induced matchings in subcubic planar graphs

R.J. Kang, M. Mnich, T. Muller

Research output: Contribution to journalArticleAcademicpeer-review

11 Citations (Scopus)
83 Downloads (Pure)

Abstract

We present a linear-time algorithm that, given a planar graph with m edges and maximum degree 3, finds an induced matching of size at least m/9. This is best possible
Original languageEnglish
Pages (from-to)1383-1411
JournalSIAM Journal on Discrete Mathematics
Volume26
Issue number3
DOIs
Publication statusPublished - 2012

Fingerprint Dive into the research topics of 'Induced matchings in subcubic planar graphs'. Together they form a unique fingerprint.

Cite this