Induced matchings in subcubic planar graphs

Publikationstyp
Conference Paper
Date Issued
2010-11-22
Sprache
English
Author(s)
Kang, Ross J.
Mnich, Matthias
Müller, Tobias
TORE-URI
http://hdl.handle.net/11420/7626
First published in
Lecture notes in computer science
Number in series
6347 LNCS
Issue
PART 2
Start Page
112
End Page
122
Citation
18th Annual European Symposium on Algorithms, ESA 2010
Contribution to Conference
18th Annual European Symposium on Algorithms (ESA 2010)
Publisher DOI
10.1007/978-3-642-15781-3_10
Scopus ID
2-s2.0-78349263140
Publisher
Springer
ISBN of container
364-215780-7
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.
DDC Class
004: Informatik