Skip to main content
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