Skip to main content

1999 | OriginalPaper | Buchkapitel

Induced Matchings in Regular Graphs and Trees

verfasst von : Michele Zito

Erschienen in: Graph-Theoretic Concepts in Computer Science

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

This paper studies the complexity of the Maximum Induced Matching problem (MIM) in regular graphs and trees. We show that the largest induced matchings in a regular graph of degree d can be approximated with a performance ratio less than d. However MIM is NP-hard to approximate within some constant c > 1 even if the input is restricted to various classes of bounded degree and regular graphs. Finally we describe a simple algorithm providing a linear time optimal solution to MIM if the input graph is a tree.

Metadaten
Titel
Induced Matchings in Regular Graphs and Trees
verfasst von
Michele Zito
Copyright-Jahr
1999
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/3-540-46784-X_10

Neuer Inhalt