scientific article; zbMATH DE number 3641455

zbMath0413.05013MaRDI QIDQ4200070

No author found.

Publication date: 1979

Full work available at URL: https://eudml.org/doc/92089

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

polynomial algorithmacyclic digraphhamiltonian pathnumber of jumpsseries-parallel digraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (30)

Interval orders without odd crowns are defect optimal ⋮ On some complexity properties of N-free posets and posets with bounded decomposition diameter ⋮ Constructing greedy linear extensions by interchanging chains ⋮ NP-completeness results concerning greedy and super greedy linear extensions ⋮ A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders ⋮ On finding the jump number of a partial order by substitution decomposition ⋮ A linear algorithm to decompose inheritance graphs into modules ⋮ N-free posets as generalizations of series-parallel posets ⋮ Greedy posets for the bump-minimizing problem ⋮ Substitution and atomic extension on greedy posets ⋮ The setup polyhedron of series-parallel posets ⋮ The arboreal jump number of an order ⋮ Minimizing the sum cost in linear extensions of a poset ⋮ Optimal Linear Extensions by Interchanging Chains ⋮ Greedy balanced pairs in \(N\)-free ordered sets ⋮ Minimizing Setups for Cycle-Free Ordered Sets ⋮ On minimizing jumps for ordered sets ⋮ The jump number of Z-free ordered sets ⋮ NP-completeness properties about linear extensions ⋮ Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings ⋮ Greedy linear extensions with constraints ⋮ Minimizing Setups for Ordered Sets: A Linear Algebraic Approach ⋮ Jump number of dags having Dilworth number 2 ⋮ Minimizing completion time for a class of scheduling problems ⋮ Jump number problem: The role of matroids ⋮ Minimizing the jump number for partially ordered sets: A graph-theoretic approach ⋮ Greedy linear extensions to minimize jumps ⋮ On the greedy dimension of a partial order ⋮ A setup heuristic for interval orders ⋮ An algorithm for minimizing setups in precedence constrained scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Series-parallel graphs and lattices
• Graph derivatives
• The dependence graph for bases in matroids
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints

This page was built for publication: