Induced matchings in subcubic planar graphs

R.J. Kang, M. Mnich, T. Müller

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

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
Title of host publicationAlgorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II)
EditorsM. Berg, de, U. Meyer
Place of PublicationBerlin
PublisherSpringer
Pages112-122
ISBN (Print)978-3-642-15780-6
DOIs
Publication statusPublished - 2010

Publication series

NameLecture Notes in Computer Science
Volume6347
ISSN (Print)0302-9743

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

Cite this