Timeline for Term for a graph decomposition based on a maximum matching
Current License: CC BY-SA 4.0
8 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Jul 28, 2019 at 16:05 | vote | accept | Erel Segal-Halevi | ||
Jul 5, 2019 at 10:34 | answer | added | Thomas Klimpel | timeline score: 0 | |
Jul 5, 2019 at 10:02 | comment | added | Erel Segal-Halevi | @ThomasKlimpel I also read the original paper: cambridge.org/core/services/aop-cambridge-core/content/view/… but I did not understand the connection - they talk about exterior covering and other concepts that I cannot see their connection to my construction. | |
Jul 5, 2019 at 5:49 | comment | added | Erel Segal-Halevi | @ThomasKlimpel I read this link but did not understand the construction. The construction is based on "D - the set of vertices in G that are not matched in at least one maximum matching of G". Apparently, to find this D (or even to verify whether a given set is D) one has to find all maximum matchings in G, which is quite hard. In contrast, my construction requires only a single maximum matching. | |
Jul 5, 2019 at 5:23 | comment | added | Thomas Klimpel | Here is a working link: Dulmage–Mendelsohn decomposition | |
Jul 5, 2019 at 0:12 | comment | added | Thomas Klimpel | Do you know en.wikipedia.org/wiki/Dulmage%E2%80%93Mendelsohn_decomposition ? It seems closely related to your decomposition. It is something like the strongly connected components of the directed graph, generated from the matching which is used for orienting the edges of the bipartite graph. | |
Jul 5, 2019 at 0:00 | history | tweeted | twitter.com/StackCompSci/status/1146931812087795712 | ||
Jul 4, 2019 at 17:26 | history | asked | Erel Segal-Halevi | CC BY-SA 4.0 |