Bipartite permutation graphs with application to the minimum buffer size problem

DOI10.1016/S0166-218X(96)00014-5MaRDI QIDQ678867zbMATH OpenFDO

Authors Ten H. Lai, Shu-Shang Wei

Publication date 9 October 1997

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

bipartite permutation graphsrelational database systems

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10) Queues and service in operations research (90B22)

Recommendations

• Bipartite permutation graphs
• scientific article; zbMATH DE number 1156661
• Efficient parallel algorithms for bipartite permutation graphs

Cites work

• A structure theorem for the consecutive 1's property
• Algorithms for Page Retrieval and Hamiltonian Paths on Forward-Convex Line Graphs
• Bipartite permutation graphs
• Heuristics for join processing using nonclustered indexes
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Use of graph-theoretic models for optimal relational database accesses to perform join

Cited in

(20)

• Bandwidth of bipartite permutation graphs in polynomial time
• Bipartite permutation graphs
• \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs
• Algorithms for maximum internal spanning tree problem for some graph classes
• Algorithm and hardness results on hop domination in graphs
• Linear structure of bipartite permutation graphs and the longest path problem
• Acyclically pushable bipartite permutation digraphs: an algorithm
• On computing longest paths in small graph classes
• On the OBDD representation of some graph classes
• Methods of local optimization for the problem of permutating bipartite graphs
• scientific article; zbMATH DE number 1156661 (Why is no real title available?)
• Acyclic matchings in subclasses of bipartite graphs
• Circularly compatible ones, D-circularity, and proper circular-arc bigraphs
• Labelled well-quasi-order for permutation classes
• On the complexity of minimum maximal uniquely restricted matching
• Critical properties of bipartite permutation graphs
• L(2,1)-labeling of perfect elimination bipartite graphs
• Vertex-edge domination in interval and bipartite permutation graphs
• Characterizing optimal monitoring edge-geodetic sets for some structured graph classes
• L(0,1)-labelling of permutation graphs

This page was built for publication: Bipartite permutation graphs with application to the minimum buffer size problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q678867)