Bipartite permutation graphs with application to the minimum buffer size problem

DOI10.1016/S0166-218X(96)00014-5zbMATH Open0873.68168MaRDI QIDQ678867FDOQ678867

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

Recommendations

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

zbMATH Keywords

bipartite permutation graphsrelational database systems

Mathematics Subject Classification ID

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

Cites Work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• 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
• 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 (17)

• Linear structure of bipartite permutation graphs and the longest path problem
• Critical properties of bipartite permutation graphs
• \(L(2, 1)\)-labeling of permutation and bipartite permutation graphs
• Bandwidth of bipartite permutation graphs in polynomial time
• Algorithm and hardness results on hop domination in graphs
• \(L(2,1)\)-labeling of perfect elimination bipartite graphs
• Acyclic matchings in subclasses of bipartite graphs
• Bipartite permutation graphs
• On computing longest paths in small graph classes
• Labelled well-quasi-order for permutation classes
• On the OBDD representation of some graph classes
• Acyclically pushable bipartite permutation digraphs: an algorithm
• \(L(0,1)\)-labelling of permutation graphs
• Methods of local optimization for the problem of permutating bipartite graphs
• On the complexity of minimum maximal uniquely restricted matching
• Circularly compatible ones, \(D\)-circularity, and proper circular-arc bigraphs
• Algorithms for maximum internal spanning tree problem for some graph classes

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)