Options
Induced matchings in subcubic planar graphs
Publikationstyp
Conference Paper
Publikationsdatum
2010-11-22
Sprache
English
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