Timeline for How can I transform every graph into one with constant out-degree?
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 6 at 14:55 | comment | added | user528933 | @BillBradley that is true. I could just make a complete graph. I wanted an easier solution XD, because in the end I have to make sure the shortest path does not change. | |
| Jun 6 at 14:53 | comment | added | user528933 | @MaxAlekseyev the function requires constant out-degree. That means that every out-degree from every vertex needs to be the same. The idea to replace it with a complete graph with 3 vertices is interesting. I need to adjust the other vertices accordingly, but that might work | |
| Jun 5 at 14:45 | comment | added | Max Alekseyev | When a vertex has out-degree 0, you can replace it with a complete directed graph on 3 vertices where each vertex has out-degree 2 (as in the cycles you introduce). | |
| Jun 5 at 13:52 | comment | added | Bill Bradley | Just to make sure I understand this, you have a directed graph and you'd like to add directed edges so that the out-degree at every node is constant? If you added all possible edges (i.e., extended to the complete directed graph), you're done. But I take it that's not what you're looking for. So, do you also want to minimize the number of edges you add? (I think that's equivalent to minimizing the final out-degree.) And would you be willing to add a few extra nodes to your graph if it further reduced the out-degree? | |
| Jun 5 at 12:53 | comment | added | Max Alekseyev | Why do you care about the same degree while you mention that only out-degree should be the same? | |
| Jun 5 at 12:51 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
added 197 characters in body
|
| Jun 4 at 12:20 | history | edited | gmvh |
Added top-level tag and "computer-science" tag
|
|
| S Jun 4 at 11:33 | review | First questions | |||
| Jun 4 at 12:14 | |||||
| S Jun 4 at 11:33 | history | asked | user528933 | CC BY-SA 4.0 |