| Project details |
Matchings and perfect matchings have received considerable attention in graph theory as well as in other related domains (such as, but not limited to, algorithms and optimization). There still remain many open problems — such as Barnette’s conjecture, Berge-Fulkerson conjecture, and so on — due to which it continues to remain an active area of research. For problems concerning perfect matchings, it is well-known that it suffices to solve them for matching covered graphs (that is, those connected graphs wherein each edge belongs to some perfect matching). The objective of this project is to implement efficient algorithms pertaining to the canonical partition, tight cut decomposition, dependency relations, (optimal) ear decomposition, brick and brace generation methods and related concepts in the theory of matching covered graphs, and to make all of these available freely to students, educators as well as researchers all across the world.
|