Induced matchings in subcubic planar graphs

Ross J. Kang; Matthias Mnich; Tobias Müller

doi:10.1137/100808824

Induced matchings in subcubic planar graphs

Ross J. Kang^*, Matthias Mnich, Tobias Müller

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

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 language	English
Pages (from-to)	1383-1411
Journal	Siam Journal on Discrete Mathematics
Volume	26
Issue number	3
DOIs	https://doi.org/10.1137/100808824
Publication status	Published - 2012
Externally published	Yes

Access to Document

10.1137/100808824

Cite this

@article{1e503e452bab480a811cb274b3bdac4a,

title = "Induced matchings in subcubic planar graphs",

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.",

author = "Kang, {Ross J.} and Matthias Mnich and Tobias M{\"u}ller",

year = "2012",

doi = "10.1137/100808824",

language = "English",

volume = "26",

pages = "1383--1411",

journal = "Siam Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "SIAM Publications",

number = "3",

}

TY - JOUR

T1 - Induced matchings in subcubic planar graphs

AU - Kang, Ross J.

AU - Mnich, Matthias

AU - Müller, Tobias

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1137/100808824

DO - 10.1137/100808824

M3 - Article

SN - 0895-4801

VL - 26

SP - 1383

EP - 1411

JO - Siam Journal on Discrete Mathematics

JF - Siam Journal on Discrete Mathematics

IS - 3

ER -