Approximating weighted induced matchings
An induced matching is a matching where no two edges are connected by a third edge. Finding a maximum induced matching on graphs with maximum degree Δ for Δ≥3, is known to be NP-complete. In this work we consider the weighted version of this problem, which has not been extensively studied in the lit...
Guardado en:
| Publicado: |
2018
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v243_n_p304_Lin http://hdl.handle.net/20.500.12110/paper_0166218X_v243_n_p304_Lin |
| Aporte de: |
Ejemplares similares
-
Approximating weighted induced matchings
por: Lin, M.C., et al. -
Fast algorithms for some dominating induced matching problems
Publicado: (2014) -
Fast algorithms for some dominating induced matching problems
por: Lin, M.C., et al. -
O(n) time algorithms for dominating induced matching problems
Publicado: (2014) -
O(n) time algorithms for dominating induced matching problems
por: Lin, M.C., et al.