Biconvex graphs: Ordering and algorithms
type: Item
instance of: scholarly article
title: Biconvex graphs: Ordering and algorithms
zbMATH Open document ID: 0977.68064
DOI: 10.1016/S0166-218X(99)00217-6
author: Nesrine Abbas
author: Lorna Stewart
published in: Discrete Applied Mathematics
publication date: 2000-07-11T00:00:00Z
review text: The authors show that the vertices of biconvex graphs have a so called S-ordering that is biconvex and generalizes a strong ordering property that is achievable for bipartite permutation graphs. A graph is biconvex when it is bipartite and allows a biconvex ordering, i.e., both bipartite sets can be ordered such that for every vertex its neighbours occur consecutively in the ordering. Moreover, a parallel algorithm is given that allows to find an S-ordering efficiently. Some applications of this result are shown. For an example the polynomial time solvability of the vertex ranking problem on biconvex graphs. This problem is to find a coloring of the vertices using a minimal number of colors such that every path between two vertices of the same color must contain a vertex with a higher color.
reviewed by: Martin Middendorf
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 1474724
zbMATH Keywords: biconvex graphs
zbMATH Keywords: S-ordering
MaRDI profile type: Publication
cites work: Rankings of Graphs
cites work: Q4942652
cites work: Polygon Graph Recognition
cites work: Characterizations of strongly chordal graphs
cites work: Maximum matching in a convex bipartite graph
cites work: Q3328583
cites work: Efficient Parallel Algorithms for Chordal Graphs
cites work: Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
cites work: Bipartite permutation graphs
cites work: A structure theorem for the consecutive 1's property
cites work: Efficient parallel algorithms for doubly convex-bipartite graphs
Wikidata QID: Q127780862
description: scientific article; zbMATH DE number 1474724