search

jgrapht / jgrapht

Master repository for the JGraphT project
http://www.jgrapht.org
Eclipse Public License 2.0
2.58k stars 822 forks source link

Comparability graphs #794

Open Aimmig opened 5 years ago

Aimmig commented 5 years ago

Is there currently an algorithm for the detection of comparability graphs - sometimes known as transitively orientable graphs - https://en.wikipedia.org/wiki/Comparability_graph or algorithms for efficient solving of common graph problems for this type of graph?

They form a subclass of perfect graphs and there are (similar to chordal graphs) linear time algorithms for finding the maximum clique & minimal coloring. Using the transitive orientation a network can be constructed so that the independent set problem and the clique cover problem can also be solved in polynomial time (using a minimum flow algorithm).

These graphs often occur when the edges of graph (naturally) define an ordering of the vertices (as the name suggest).

jsichi commented 5 years ago

The only related work we have so far is #582 on interval graphs, which seems to have run aground after a very lengthy review cycle.

If you want to work on this, it will be good to sketch out any plans in detail here before you start coding.