Interval graph detection #545
Labels
Comments
|
That would certainly be interesting.
It would be nice to have a class which builds an interval graph from a list
of intervals. Moreover, we indeed could use a detection algorithm which
detects whether a graph is an interval graph. This algorithm must prove
(certify) that the graph is or isn't an interval graph. If it is an
interval graph, then the algorithm must provide an embedding (interval for
every vertex). Perhaps Sage math (
http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.is_interval)
could provide some inspiration.
Finally, if you end up implementing such a detection mechanism, make sure
you add the following method to GraphTests:
boolean GraphTests.isIntervalGraph(Graph<V,E> graph) which returns true if
the graph is an interval graph, false otherwise.
Before you get started, read our brand new Developer Pages:
https://github.com/jgrapht/jgrapht/wiki#developer-pages
I am not up-to-date with recognition algorithms for Interval Graphs, so it
might be a good idea to do a bit of literature research to see what's out
there.
br,
Joris Kinable
…On Tue, Apr 10, 2018 at 6:04 PM, Dennis Fischer ***@***.***> wrote:
Hello!
As part of a practical course at my university my team wants to contribute
to JGraphT. The first thing we are interested in is the detection of
interval graphs.
Interval graphs are the intersection graphs of intervals on a line. Almost
all well known problems on graphs are efficiently solvable on those graphs.
The detection algorithm should output a interval representation if the
graph is an interval graph, or provide a proof if it is not. The algorithm
that is probably best suited is the one proposed in here
<https://www.sciencedirect.com/science/article/pii/S0304397597002417>.
Is this something that fits the scope of JGraphT?
It should also be possible to directly create graph instances by providing
the interval representation of a graph.
The next steps would be the implementation of fast algorithms for interval
graphs.
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
<#545>, or mute the thread
<https://github.com/notifications/unsubscribe-auth/ACnYythev30RBEGy9iV8T24dJcD6ODUxks5tnNgcgaJpZM4TOjte>
.
|
This was referenced May 30, 2018
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hello!
As part of a practical course at my university my team wants to contribute to JGraphT. The first thing we are interested in is the detection of interval graphs.
Interval graphs are the intersection graphs of intervals on a line. Almost all well known problems on graphs are efficiently solvable on those graphs.
The detection algorithm should output a interval representation if the graph is an interval graph, or provide a proof if it is not. The algorithm that is probably best suited is the one proposed in here.
Is this something that fits the scope of JGraphT?
It should also be possible to directly create graph instances by providing the interval representation of a graph.
The next steps would be the implementation of fast algorithms for interval graphs.
The text was updated successfully, but these errors were encountered: