A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders

DOI10.1007/BF00340778zbMath0622.06002MaRDI QIDQ1090688

George Steiner, Lorna K. Stewart

Publication date: 1987

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

linear algorithm; jump number problem; 2-dimensional bipartite posets

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

06A06: Partial orders, general

Related Items

Visibility graphs of towers, A 3/2-approximation algorithm for the jump number of interval orders, Bipartite permutation graphs, On minimizing jumps for ordered sets, The jump number of Z-free ordered sets, Maximum and minimum jump number of posets from matrices, On a setup optimization problem for interval orders, Line directionality of orders, Alternating cycle-free matchings, On edge perfectness and classes of bipartite graphs, Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings

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