Induced matchings in subcubic planar graphs

Link:
Autor/in:
Verlag/Körperschaft:
Hamburg University of Technology
Erscheinungsjahr:
2010
Medientyp:
Text
Schlagwort:
  • 004: Informatik
Beschreibung:
  • 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.
Beziehungen:
DOI 10.1007/978-3-642-15781-3_10
Quellsystem:
TUHH Open Research
Interne Metadaten
Quelldatensatz
oai:tore.tuhh.de:11420/7626