Timeline for Reduce the total internal border of a set of touching rectangles (using graphs)
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 28, 2018 at 6:53 | answer | added | jozamm | timeline score: 1 | |
| Dec 14, 2018 at 17:35 | history | edited | jozamm | CC BY-SA 4.0 |
Added picture of an actual structure, Each yellow rectangle (in the last diagram) will have an extension added to it.
|
| Dec 14, 2018 at 17:12 | history | edited | jozamm | CC BY-SA 4.0 |
Post picture of a an actual structure
|
| Dec 13, 2018 at 21:56 | answer | added | John | timeline score: 1 | |
| Dec 13, 2018 at 21:23 | comment | added | John | Branch and bound might be the easiest way to go here. It's exam week, so I'm not completely thinking straight, but I don't see either an obvious dynamic programming solution, nor an obvious NP-completeness proof here. | |
| Dec 13, 2018 at 21:13 | comment | added | John | The dual graph representation doesn't seem to encode enough information. Consider your optimal solution for the first example, and think about it being some sub-part of a larger figure. In that case, none of the edges of the graph actually encode allowable contractions because the rectangles aren't connected along entire edges. | |
| Dec 13, 2018 at 12:15 | review | First posts | |||
| Dec 13, 2018 at 15:56 | |||||
| Dec 13, 2018 at 12:12 | history | asked | jozamm | CC BY-SA 4.0 |