Timeline for Has anyone seen a NP graph problem like this before?
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 19, 2020 at 4:27 | comment | added | ShAr | In ur problem, do u consider independent vertices included in "at least L distance"? I mean maybe it depends on the original practical problem u r solving, does completely not reachable means distance=infinity and thus included in at least L???? | |
| Apr 18, 2020 at 21:21 | comment | added | qalis | Well, it sounds quite reasonable, I'll try it! I have also had another thought: my graph may have disconnected components. How would you go about ensuring that I get one color "most popular" across all components? I mean, for 2 components for example for simple greedy heuristic one component may get mostly one of the L colors (good candidate for color for those K vertices), on the second component other one gets most color and I get no solution. Is there a way I can save from that? | |
| Apr 18, 2020 at 21:15 | history | answered | ShAr | CC BY-SA 4.0 |