Timeline for Breaking frustrated loops in list coloring problem
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 10, 2011 at 19:07 | comment | added | Yaroslav Bulatov | I unfortunately don't know any related literature, this is a theoretical example for a practical problem that arises when running a particular message passing algorithm on graph. Frustrated cycles cause convergence problems and I can delete a few nodes and correct for their removal. There's a bounded number of nodes I can afford to remove, so I want to break as many frustrated cycles as possible with that number. | |
| Jan 10, 2011 at 16:31 | answer | added | Tony Huynh | timeline score: 2 | |
| Jan 10, 2011 at 4:30 | comment | added | Gerhard Paseman | If (a few) lists of size 1 are allowed, there are also interesting examples of trees with no proper list coloring. It might be a good idea for you to provide some examples so that "small", "large", are made clear. Also a few words on the obstacle characterization would be appreciated. Do you want to eventually break all cycles? Or are you content with a maximal colorable subgraph? Also, it would help if you contrasted your problem with known literature, so that experts can suggest alternatives that you want. Gerhard "Ask Me About System Design" Paseman, 2011.01.09 | |
| Jan 10, 2011 at 2:25 | history | edited | Yaroslav Bulatov | CC BY-SA 2.5 |
added 3 characters in body
|
| Jan 9, 2011 at 22:53 | history | asked | Yaroslav Bulatov | CC BY-SA 2.5 |