Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing.
Michel HabibRoss M. McConnellChristophe PaulLaurent ViennotPublished in: Theor. Comput. Sci. (2000)
Keyphrases
- breadth first search
- recognition rate
- partitioning algorithm
- recognition accuracy
- depth first search
- object recognition
- feature extraction
- pattern recognition
- weighted graph
- normalized cut
- automatic recognition
- directed graph
- activity recognition
- recognition algorithm
- connected components
- vertex set
- min cut
- random walk
- graph structure
- directed acyclic graph
- undirected graph
- transitive closure