Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
type: Item
instance of: scholarly article
title: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
zbMATH Open document ID: 0945.68189
DOI: 10.1016/S0304-3975(97)00241-7
author: N. Delaunay
published in: Theoretical Computer Science
publication date: 2000-08-21T00:00:00Z
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 1493450
zbMATH Keywords: algorithm
zbMATH Keywords: data-structure
zbMATH Keywords: partition refinement
zbMATH Keywords: graph
zbMATH Keywords: Boolean matrix
Wikidata QID: Q55952669
MaRDI profile type: Publication
cites work: Q5615282
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Classes of bipartite graphs related to chordal graphs
cites work: Q4954442
cites work: Q5501779
cites work: Transitiv orientierbare Graphen
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: The edge inducibility of graphs
cites work: An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
cites work: Q3128916
cites work: Three Partition Refinement Algorithms
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
full work available at URL: s0304-3975(97)00241-7
OpenAlex ID: W2161426837
description: scientific article; zbMATH DE number 1493450