Anzeige
Erschienen in:
2023 | OriginalPaper | Buchkapitel
Vertex Ordering with Precedence Constraints
verfasst von : Jeff Kinne, Akbar Rafiey, Arash Rafiey, Mohammad Sorkhpar
Erschienen in: Fundamentals of Computation Theory
Verlag: Springer Nature Switzerland
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We study bipartite graph ordering problem, which arises in various domains such as production management, bioinformatics, and job scheduling with precedence constraints. In the bipartite vertex ordering problem, we are given a bipartite graph \(H=(B, S,E)\) where each vertex in B has a cost and each vertex in S has a profit. The goal is to find a minimum K together with an ordering < of the vertices of H, so that \(i<j\) whenever \(i \in B\) is adjacent to \(j \in S\). Moreover, at each sub-order the difference between the costs and profits of the vertices in the sub-order does not exceed K.
The bipartite ordering problem is NP-complete when the weights are one, and the bipartite graph H is a bipartite circle graph. This restricted version was used in the study of the secondary structure of RNA in [11].
Thus, we seek exact algorithms for solving the bipartite ordering problem in classes with simpler structures than bipartite circle graphs. We give non-trivial polynomial time algorithms for finding the optimal solutions for bipartite permutation graphs, bipartite trivially perfect graphs, bipartite cographs, and trees. There are still several classes of bipartite graphs for which the ordering problem could be polynomial, such as bipartite interval graphs, bipartite convex graphs, bipartite chordal graphs, etc.
In addition, we formulate the problem as a linear programming (LP) model and conduct experiments on random instances. We did not find any example with an integrality gap of two or more when limited to bipartite circle graphs with unit weights. No example with an integrality gap of more than 5/2 was found for arbitrary bipartite graphs with random weights. It would be interesting to investigate the possibility of designing a constant approximation algorithm for this problem.