search

adamsardar / stoneTrees

Integrating 'omics data with biological networks by solving Steiner Tree problems
Mozilla Public License 2.0
3 stars 3 forks source link

Add connectivity constraints preemptively? #21

Open adamsardar opened 4 years ago

adamsardar commented 4 years ago

The node separator concept makes it's appearance in a paper from the late 80's. Take the seeds, one-hop out, break into connected components and then add node-separator constraints. This might guide the solver a little and stop so many disconnected components being produced.

See: Heuristics for the Steiner problemin graphs (plesnik) [1989] - https://core.ac.uk/download/pdf/82609861.pdf

adamsardar commented 4 years ago

Turns out that Steiner trees are contained within the APSP set of seeds: see Steiner distance and convexity in graphs [2007]. Here's a link to a paper

Worth reflecting on whether there is a concept of 'Steiner+1' convexity, where sub-optimal (tolerance of 1) solutions are contained.