Induced matchings in subcubic planar graphs

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

11 Citaten (Scopus)
167 Downloads (Pure)

Samenvatting

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
Originele taal-2Engels
Pagina's (van-tot)1383-1411
TijdschriftSIAM Journal on Discrete Mathematics
Volume26
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 2012

Vingerafdruk

Duik in de onderzoeksthema's van 'Induced matchings in subcubic planar graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit