{"id":1999,"date":"2021-04-13T11:39:00","date_gmt":"2021-04-13T10:39:00","guid":{"rendered":"http:\/\/sites.maths.cf.ac.uk\/mathsugprojects\/?p=1999"},"modified":"2022-11-11T10:24:54","modified_gmt":"2022-11-11T10:24:54","slug":"alternate-paths-and-matchings-in-graphs-supervisor-dr-andrei-gagarin","status":"publish","type":"post","link":"https:\/\/sites.maths.cf.ac.uk\/mathsugprojects\/alternate-paths-and-matchings-in-graphs-supervisor-dr-andrei-gagarin\/","title":{"rendered":"Alternate paths and matchings in graphs – Supervisor: Dr Andrei Gagarin"},"content":{"rendered":"\n

Project title:<\/strong> Alternating paths and matchings in\ngraphs<\/p>\n\n\n\n

Name of supervisor:<\/strong> Dr Andrei Gagarin<\/p>\n\n\n\n

Code:<\/strong> AG2122A<\/p>\n\n\n\n

Project Description:<\/strong><\/p>\n\n\n\n

Background<\/p>\n\n\n\n

Matchings play an important role in graph theory and applications, for example, in assignment problems, where pairs of items are to be matched together (e.g. if people are to be assigned to jobs). The problem of finding a maximum (by cardinality) matching in a given graph G=(V,E) is solvable in polynomial time. The Hungarian algorithm allows us to find a maximum-size matching in a bipartite graph, and the Edmonds\u2019 blossoms algorithm extends the ideas of efficient usage of alternating paths to non-bipartite graphs. A variation of the problem consists in finding a smallest weight\/cost maximum matching in weighted graphs.<\/p>\n\n\n\n

Objectives<\/p>\n\n\n\n

The objectives of this project consist in studying literature related to the theory of matchings and alternating paths in graphs, their applications, and the Hungarian algorithm and the Edmonds\u2019 blossoms algorithm to find a maximum matching in a graph. The student will need to implement the Hungarian algorithm and run experiments on either artificially generated or some real-world instances of the problem. Another objective is to study the Edmonds\u2019 blossoms algorithm and to understand the proof of its correctness. The minimum\/maximum cost maximum-size matchings in weighted graphs and integer linear problem formulations are to be considered as well.<\/p>\n\n\n\n

Approach<\/p>\n\n\n\n

Study of literature on alternating paths and matchings from the points of view of Graph Theory, algorithms, and applications. Implementing the Hungarian algorithm and running computational experiments on some artificially generated or real-world instances and comparing the computational outcomes. Considering maximum-size matchings in weighted graphs and integer linear programming formulations of the problems, using generic LP\/IP solvers.<\/p>\n\n\n\n

References:<\/strong><\/p>\n\n\n\n

1.            W.L. Kocay, D.L. Kreher, Graphs, Algorithms, and Optimization<\/em>, 2nd ed., CRC Press, 2017, Chapter 9.<\/p>\n\n\n\n

2.            D. Karapetyan, A.J. Parkes, G. Gutin, A. Gagarin, Pattern-based approach to the workflow satisfiability problem with user-independent constraints, Journal of Artificial Intelligence Research<\/em> 66 (2019), pp. 85-122.<\/p>\n\n\n\n

3. W.L. Winston, Operations Research: applications and algorithms<\/em>, 4th<\/sup> ed., Thomson-Brooks\/Cole, 2004, Section 7.5.3.<\/p>\n\n\n\n

Deliverables<\/strong><\/p>\n\n\n\n

A report (dissertation\/thesis) and software implementing the Hungarian algorithm to solve the problem in weighted and\/or unweighted graphs, together with problem instances used in computational experiments.<\/p>\n\n\n\n

Prerequisites<\/strong><\/p>\n\n\n\n

An interest in and some knowledge of graph theory, modeling of real-life problems on graphs, as well as some computer programming skills using data structures to solve problems on graphs and combinatorial structures.<\/p>\n","protected":false},"excerpt":{"rendered":"

Project title: Alternating paths and matchings in graphs Name of supervisor: Dr Andrei Gagarin Code: AG2122A Project Description: Background Matchings play an important role in graph theory and applications, for example, in assignment problems, where pairs of items are to be matched together (e.g. if people are to be assigned to jobs). The problem of … Continue reading Alternate paths and matchings in graphs – Supervisor: Dr Andrei Gagarin<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":5,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[2,8],"tags":[],"class_list":["post-1999","post","type-post","status-publish","format-standard","hentry","category-2021-2022","category-yr-4-description-2021-2022"],"aioseo_notices":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/sites.maths.cf.ac.uk\/mathsugprojects\/wp-json\/wp\/v2\/posts\/1999","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.maths.cf.ac.uk\/mathsugprojects\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.maths.cf.ac.uk\/mathsugprojects\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.maths.cf.ac.uk\/mathsugprojects\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.maths.cf.ac.uk\/mathsugprojects\/wp-json\/wp\/v2\/comments?post=1999"}],"version-history":[{"count":3,"href":"https:\/\/sites.maths.cf.ac.uk\/mathsugprojects\/wp-json\/wp\/v2\/posts\/1999\/revisions"}],"predecessor-version":[{"id":2084,"href":"https:\/\/sites.maths.cf.ac.uk\/mathsugprojects\/wp-json\/wp\/v2\/posts\/1999\/revisions\/2084"}],"wp:attachment":[{"href":"https:\/\/sites.maths.cf.ac.uk\/mathsugprojects\/wp-json\/wp\/v2\/media?parent=1999"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.maths.cf.ac.uk\/mathsugprojects\/wp-json\/wp\/v2\/categories?post=1999"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.maths.cf.ac.uk\/mathsugprojects\/wp-json\/wp\/v2\/tags?post=1999"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}