On the Complexity of Computing a Maximum Acyclic Matching in Undirected Graphs
The problem of finding a maximum acyclic matching in a simple undirected graph is known to be NP-complete. In this paper, we present new results; we show that a maximum acyclic matching in a given undirected graph (with <i>n</i> vertices and <i>m</i> edges) can be computed re...
| Hlavní autor: | |
|---|---|
| Médium: | Článek |
| Jazyk: | English |
| Vydáno: |
MDPI AG
2025-03-01
|
| Edice: | Mathematics |
| Témata: | |
| On-line přístup: | https://www.mdpi.com/2227-7390/13/5/889 |