Timeline for Perfect matching decomposition algorithm for bipartite regular graphs
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 10, 2022 at 13:40 | comment | added | AspiringMat | @EmilJeřábek Yes, my initial comment was on just a single matching, but for the entire decomposition, you get an extra log factor in there as you mention, thanks for adding. | |
| Aug 10, 2022 at 8:15 | history | edited | YCor | CC BY-SA 4.0 |
removed capitals from title
|
| Aug 10, 2022 at 8:09 | comment | added | Emil Jeřábek | I meant $O(m\log d)$, not $O(m\log m)$. | |
| Aug 10, 2022 at 8:03 | comment | added | Emil Jeřábek | But note that even in the power of 2 case, you need to recursively process both halves of the graph to get a decomposition. Thus, this will be time $O(m\log m)$ rather than $O(m)$. This time bound holds for general $d$ as well (finding perfect matchings in regular bipartite graphs can be done in time $O(m)$). | |
| Aug 10, 2022 at 7:56 | comment | added | Emil Jeřábek | @AspiringMat Good idea. You can use it even if $d$ is not a power of $2$: if $d$ is even, find an Eulerian cycle as you describe, halving the degree; if $d$ is odd, find and remove a perfect matching first, making $d$ even. Then repeat. | |
| Aug 10, 2022 at 6:47 | comment | added | AspiringMat | Specifically, find an Eulerian cycle and remove m/2 edges from B to A. You get a d/2 regular graph with m/2 edges. Repeat recursively until you have your matching | |
| Aug 10, 2022 at 6:42 | comment | added | AspiringMat | If the graph is $d$ Regular for $d$ Power of 2, then there is a nice linear time algorithm (O($m$)) time | |
| Aug 10, 2022 at 6:20 | comment | added | Emil Jeřábek | The standard proof of the result already gives a simple polynomial-time algorithm: find a perfect matching, remove it from the graph (which preserves its being regular bipartite), rinse and repeat until the graph is empty. I don’t know if there is anything more efficient. | |
| S Aug 10, 2022 at 5:28 | review | First questions | |||
| Aug 10, 2022 at 5:53 | |||||
| S Aug 10, 2022 at 5:28 | history | asked | CCC | CC BY-SA 4.0 |