On computing maximum size matchings in graphs
| dc.contributor.author | Schoppmeyer, Andreas | |
| dc.date.accessioned | 2006-12-07T15:43:38Z | |
| dc.date.available | 2006-12-07T15:43:38Z | |
| dc.date.issued | 2006 | |
| dc.description.abstract | The problem of finding a maximum-size matching in a graph appears in many situations in graph theory. Therefore it is crucial to compute such matchings in a fast way. In some cases a hybrid algorithm, consisting of an heuristic to find a start-matching and an exact algorithm to compute the maximum-size matching, appears to be much faster than classical algorithms. We show a way to implement appropriate heuristics, exact algorithms and hybrid algorithms in C++ and compare their performance on different random graphs. To reduce the programming-effort , we used comprehensible techniques. These techniques can be implemented indepen- dent of programming languages and the operating systems. | en |
| dc.format.extent | 92268 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/2003/23117 | |
| dc.identifier.uri | http://dx.doi.org/10.17877/DE290R-3076 | |
| dc.language.iso | en | |
| dc.publisher | Universität Dortmund, Wirtschafts- und Sozialwissenschaftliche Fakultät | de |
| dc.relation.ispartofseries | Diskussionsbeiträge des Fachgebietes Operations Research und Wirtschaftsinformatik;32 (2006) | |
| dc.subject | Efficient graph algoritms | en |
| dc.subject | Maximun-size matchings | en |
| dc.subject.ddc | 330 | |
| dc.title | On computing maximum size matchings in graphs | en |
| dc.type | Text | de |
| dc.type.publicationtype | workingPaper | |
| dcterms.accessRights | open access |