Induced matchings in subcubic planar graphs

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

doi:10.1137/100808824

Induced matchings in subcubic planar graphs

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

Combinatorial Optimization

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

12 Citations (Scopus)

408 Downloads (Pure)

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

Access to Document

10.1137/100808824

publishers versionFinal published version, 533 KB

Cite this

@article{db2ca1831f83412d9f4a6c59bbaeef51,

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 = "R.J. Kang and M. Mnich and T. Muller",

year = "2012",

doi = "10.1137/100808824",

language = "English",

volume = "26",

pages = "1383--1411",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

number = "3",

}

TY - JOUR

T1 - Induced matchings in subcubic planar graphs

AU - Kang, R.J.

AU - Mnich, M.

AU - Muller, T.

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 -

Induced matchings in subcubic planar graphs

Abstract

Access to Document

Fingerprint

Cite this