N-free posets as generalizations of series-parallel posets

DOI10.1016/0166-218X(85)90030-7zbMath0635.06002MaRDI QIDQ1097286

Michel A. Habib, Roland Jégou

Publication date: 1985

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

algorithmN-free posetsseries-parallel posets

Mathematics Subject Classification ID

Partial orders, general (06A06) Graph theory (05C99)

Related Items

On some complexity properties of N-free posets and posets with bounded decomposition diameter ⋮ Substitution and atomic extension on greedy posets ⋮ Concurrency and atomicity ⋮ Parallel \(N\)-free order recognition ⋮ Complexité de problèmes liés aux graphes sans circuit ⋮ The arboreal jump number of an order ⋮ Greedy balanced pairs in \(N\)-free ordered sets ⋮ The queue-number of posets of bounded width or height ⋮ Parallel interval order recognition and construction of interval representations ⋮ Cross-series-parallel digraphs ⋮ \(N\)-free orders and minimal interval extensions ⋮ The monadic second-order logic of graphs. XV: On a conjecture by D. Seese ⋮ Rank decomposition under zero pattern constraints and \(\mathsf{L}\)-free directed graphs ⋮ Unnamed Item ⋮ Additive decomposition of matrices under rank conditions and zero pattern constraints ⋮ Efficient polynomial algorithms for distributive lattices ⋮ Linear extensions of N-free orders.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing the jump number for partially ordered sets: A graph-theoretic approach
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• A labeling algorithm to recognize a line digraph and output its root graph
• Topology of series-parallel networks
• Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
• A Combinatorial Decomposition Theory
• The Jump Number of Dags and Posets: An Introduction
• Linear-time computability of combinatorial problems on series-parallel graphs
• Decomposition of Directed Graphs
• Ordres "C.A.C."
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Maximal chains and antichains
• Partially Ordered Sets