Timeline for Optimal paths in set-weighted graphs
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 8, 2020 at 6:29 | comment | added | JimN | without any structure in the graph paths or in the sets weights, essentially all paths woul have to be checked ... unless in a shortest path problem, where a path from s-t going through an intermediate u, it doesn't matter how s gets to u, just the value at u is important. But the unio nof all your sets along the way would be different for every s-to-u path, so essentially all paths would have to be considered. | |
| Sep 8, 2020 at 6:24 | comment | added | JimN | I have not seen this problem studied before. Sets on vertices have been used in describing graph dimension or list-colouring or preference lists in stable matching problems, for example. In general, intersection graphs are graphs where each vertex is a set and an edge represents a non-empty intersection of the two vertices. Those sets are sometimes geometrical points, or intervals of real lines, or just discrete sets. | |
| Sep 6, 2020 at 23:31 | comment | added | Rodrigo de Azevedo | Why not post at cstheory.stackexchange.com? | |
| Sep 6, 2020 at 8:51 | history | asked | Victor | CC BY-SA 4.0 |