scientific article; zbMATH DE number 3903967

MaRDI QIDQ3681937zbMATH OpenFDO

Authors K. W. Wagner

Publication date 1984

zbMATH Keywords

3SAT problemcovering functionsNP-completeness

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Covering symmetric semi-monotone functions
• Covering oriented points in the plane with orthogonal polygons is NP-complete
• NP-harte Probleme für minimale Polygonüberdeckungen. (NP-hard problems for minimal polygon coverings)
• scientific article; zbMATH DE number 1947430
• Covering a Simple Polygon by Monotone Directions

Cited in

(20)

• On minimum \(k\)-modal partitions of permutations
• An unfeasible matching problem
• On cocolourings and cochromatic numbers of graphs
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Approximating minimum cocolorings.
• Partitioning permutations into increasing and decreasing subsequences
• The mixed page number of graphs
• Fixed-parameter algorithms for the cocoloring problem
• Covering symmetric semi-monotone functions
• Partitioning cographs into cliques and stable sets
• Complete edge-colored permutation graphs
• Monotone reducibility and the family of infinite sets
• On directional monogeneity sets
• Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization
• Partitioning extended \(P_4\)-laden graphs into cliques and stable sets
• Monovex sets
• Sorting shuffled monotone sequences
• A linear time approximation algorithm for permutation flow shop scheduling
• Partitioning permutations into monotone subsequences
• A tutorial on the use of graph coloring for some problems in robotics

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3681937)