A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
From MaRDI portal
Publication:1090688
DOI10.1007/BF00340778zbMath0622.06002OpenAlexW2073598086MaRDI QIDQ1090688
Lorna K. Stewart, George Steiner
Publication date: 1987
Published in: Order (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00340778
Related Items (15)
Alternating cycle-free matchings ⋮ Bipartite permutation graphs ⋮ On edge perfectness and classes of bipartite graphs ⋮ Minimizing the sum cost in linear extensions of a poset ⋮ A 3/2-approximation algorithm for the jump number of interval orders ⋮ On minimizing jumps for ordered sets ⋮ The jump number of Z-free ordered sets ⋮ Jump Number of Two-Directional Orthogonal Ray Graphs ⋮ Visibility graphs of towers ⋮ Maximum and minimum jump number of posets from matrices ⋮ On a setup optimization problem for interval orders ⋮ Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings ⋮ Independent sets and hitting sets of bicolored rectangular families ⋮ Flip distances between graph orientations ⋮ Line directionality of orders
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimizing setups in ordered sets of fixed width
- Jump number of dags having Dilworth number 2
- Minimizing the jump number for partially ordered sets: A graph-theoretic approach
- Greedy linear extensions to minimize jumps
- Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
- Optimal Linear Extensions by Interchanging Chains
- Algorithmic Approaches to Setup Minimization
- Optimal Sequencing by Modular Decomposition: Polynomial Algorithms
- The Jump Number of Dags and Posets: An Introduction
- Minimizing Setups for Cycle-Free Ordered Sets
- Permutation Graphs and Transitive Graphs
This page was built for publication: A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
