On some complexity properties of N-free posets and posets with bounded decomposition diameter (Q1086264): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Q4773298 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Linear-time computation of optimal subgraphs of decomposable graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Fast Algorithm for the Decomposition of Graphs and Posets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4068748 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Jump Number of Dags and Posets: An Introduction / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4200070 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complement reducible graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Topology of series-parallel networks / rank
 
Normal rank
Property / cites work
 
Property / cites work: Partially Ordered Sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3329227 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Minimizing Setups for Ordered Sets: A Linear Algebraic Approach / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximal chains and antichains / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5184948 / rank
 
Normal rank
Property / cites work
 
Property / cites work: N-free posets as generalizations of series-parallel posets / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the X-join decomposition for undirected graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3872508 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5345642 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A V log V algorithm for isomorphism of triconnected planar graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3964626 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Asymptotic Enumeration of Partial Orders on a Finite Set / rank
 
Normal rank
Property / cites work
 
Property / cites work: A structured program to generate all topological sorting arrangements / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4130999 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3940839 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ordres "C.A.C." / rank
 
Normal rank
Property / cites work
 
Property / cites work: Almost all comparability graphs are UPO / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3686754 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3683903 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5187059 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal Sequencing Via Modular Decomposition: Characterization of Sequencing Functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3344241 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A labeling algorithm to recognize a line digraph and output its root graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Minimizing the jump number for partially ordered sets: A graph-theoretic approach / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3676161 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Linear-time computability of combinatorial problems on series-parallel graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Complexity of the Partial Order Dimension Problem / rank
 
Normal rank

Revision as of 16:59, 17 June 2024

scientific article
Language Label Description Also known as
English
On some complexity properties of N-free posets and posets with bounded decomposition diameter
scientific article

    Statements

    On some complexity properties of N-free posets and posets with bounded decomposition diameter (English)
    0 references
    1987
    0 references
    Among generalizations of series-parallel posets, the N-free posets are much better known than posets with bounded decomposition diameter, i.e., those posets iteratively built up by substitution from posets of cardinality at most k. Nevertheless, the authors demonstrate that the latter class may well be the better one for a variety of combinatorial optimization problems and other reasons. Thus, although the jump-number problem is shown to be polynomially solvable on both classes, the isomorphism problem and the 1/prec/\(\sum w_ jC_ j\) scheduling problem are here demonstrated to be among these which are only polynomially solvable for the second class. As an early exponent of the merits of the substitution technique, this author finds the success of the method more than only interesting. Since the subject is still in a process of evolving its main outlines, this paper will make an important difference in the direction of eventual development. To the extent that it will be superseded by further results, its very success will make its view more commonplace.
    0 references
    NP-hard
    0 references
    series-parallel posets
    0 references
    N-free posets
    0 references
    posets with bounded decomposition diameter
    0 references
    combinatorial optimization problems
    0 references
    jump-number problem
    0 references
    polynomially solvable
    0 references
    isomorphism problem
    0 references
    scheduling problem
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references