Wyniki wyszukiwania - Biblioteka Nauki

Ten serwis zostanie wyłączony 2025-02-11.

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: NP-complete

Sortuj według:

Ogranicz wyniki do:

Interactive knapsacks

100%

Aho I.

2000

tom Vol. 44, Nr 1,2

1-23

The interactive knapsack problems are generalizations of the classical knapsack problem. Three different new NP-complete problems, interactive knapsack heuristic decision problem (IKHD), interactive knapsack decision problem (IKD) and multidimensional cloned knapsack decision problem (MDCS), are presented for the interactive knapsack models. IKD and MDCS are shown to be strongly NP-complete. By using interactive knapsacks we can model many planning and scheduling problems in an innovative way. Possible application areas include electricity management, single and multiprocessor scheduling, and packing and tiling problems. As a by-product we show that the longest weight-constrained path problem is NP-complete.

Complexity of cover - preserving embeddings of bipartite orders into boolean lattices

100%

Herman G.

Reports on Mathematical Logic

2014

tom Vol. 49

99--117

We study the problem of deciding, whether a given partial order is embeddable into two consecutive layers of a Boolean lattice. Employing an equivalent condition for such em- beddability similar to the one given by J. Mittas and K. Reuter [5], we prove that the decision problem is NP-complete by showing a polynomial-time reduction from the not-all-equal variant of the Satisfiability problem.

Split Euler Tours In 4-Regular Planar Graphs

88%

Couch P. , Daniel B. D. , Guidry R. , Paul Wright W.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 1

23-30

The construction of a homing tour is known to be NP-complete. On the other hand, the Euler formula puts su cient restrictions on plane graphs that one should be able to assert the existence of such tours in some cases; in particular we focus on split Euler tours (SETs) in 3-connected, 4-regular, planar graphs (tfps). An Euler tour S in a graph G is a SET if there is a vertex v (called a half vertex of S) such that the longest portion of the tour between successive visits to v is exactly half the number of edges of G. Among other results, we establish that every tfp G having a SET S in which every vertex of G is a half vertex of S can be transformed to another tfp G′ having a SET S′ in which every vertex of G′ is a half vertex of S′ and G′ has at most one point having a face configuration of a particular class. The various results rely heavily on the structure of such graphs as determined by the Euler formula and on the construction of tfps from the octahedron. We also construct a 2-connected 4-regular planar graph that does not have a SET.

Constraint satisfaction problem based modelling and value ordering based heuristic for nurse scheduling

88%

Djeffal L. , Goncalves G. , Babes M.

tom Vol. 14, nr 2

7-28

Nurse Scheduling Problem (NSP) consists of assigning shift-types (morning, afternoon and night) to qualified personnel over a certain planning period. It is a difficult and time-consuming task. In this paper we present a formulation of the hospital Nurse Scheduling Problem just like Constraint Satisfaction Problem "CSP" based constraint programming in order to find a solution, which minimizes the violation of Nurses' preferences. We would suggest a flexibility tool for helping to decide and for making negotiation easier. Our originality lies in the modelling of the problem, by defining the global constraints and in the algorithm of resolution to solve it, by proposing a new value ordering based heuristic for assignment of the decision variables taking into account the set of Nurses preferences. Our heuristic is based on the structure of the CSP and on the properties of constraints. It allows the reduction of the search space for solution and returns a solution within few second.