Options
Induced matchings in subcubic planar graphs
Publikationstyp
Conference Paper
Date Issued
2010-11-22
Sprache
English
Author(s)
TORE-URI
First published in
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
Publisher DOI
Scopus ID
Publisher
Springer
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