PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 9

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  NP-hardness
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
Furmańczyk H., Kubale M.
Bulletin of the Polish Academy of Sciences. Technical Sciences
|
2017
|
Vol. 65, nr 1
29--34
EN
In the paper we consider the problem of scheduling n identical jobs on 4 uniform machines with speeds s1 ≥ s2 ≥ s3 ≥ s4, respectively. Our aim is to find a schedule with a minimum possible length. We assume that jobs are subject to some kind of mutual exclusion constraints modeled by a bipartite incompatibility graph of degree Δ, where two incompatible jobs cannot be processed on the same machine. We show that the general problem is NP-hard even if s1 = s2 = s3. If, however, Δ ≤ 4 and s1 ≥ 12s2, s2 = s3 = s4, then the problem can be solved to optimality in time O(n1.5). The same algorithm returns a solution of value at most 2 times optimal provided that s1 ≥ 2s2. Finally, we study the case s1 ≥ s2 ≥ s3 = s4 and give a 32/15-approximation algorithm running also in O(n1.5) time.
2
Content available Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms
Furmańczyk H., Jastrzębski A., Kubale M.
Archives of Control Sciences
|
2016
|
Vol. 26, no. 3
281--295
EN
In many applications in sequencing and scheduling it is desirable to have an underlaying graph as equitably colored as possible. In this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs.
3
Content available remote Modele i metody kolorowania grafów. Część II
Kubale M.
Przegląd Elektrotechniczny
|
2012
|
R. 88, nr 11a
51-55
PL
Niniejszy artykuł jest drugą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano różne kryteria i ograniczenia modyfikujące kolorowanie klasyczne. Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podano oszacowania na liczbę chromatyczną (indeks chromatyczny) oraz podano potencjalne zastosowania rozważanych modeli w problemach naukowo-technicznych.
EN
This is the second of a couple of review papers on models and methods of graph coloring. We present herein the main models of graph coloring from a practical point of view. In particular, we show various criteria and modifications of classical coloring model. Since graph coloring is NP-hard in various modifications and variants, we give simple bounds on the chromatic number (chromatic index) as well as we give potential applications of the chromatic methods in science and technology.
4
Content available remote Size Constrained Distance Clustering: Separation Properties and Some Complexity Results
Bertoni A., Goldwurm M., Lin J., Sacca F.
Fundamenta Informaticae
|
2012
|
Vol. 115, nr 1
125-139
EN
In this paper we study the complexity of some size constrained clustering problems with norm Lp. We obtain the following results: (i) A separation property for the constrained 2-clustering problem. This implies that the optimal solutions in the 1-dimensional case verify the so-called "String Property"; (ii) The NP-hardness of the constrained 2-clustering problem for every norm Lp (p > 1); (iii) A polynomial time algorithmfor the constrained 2-clustering problemin dimension 1 for every norm Lp with integer p. We also give evidence that this result cannot be extended to norm Lp with rational non-integer p; (iv) The NP-hardness of the constrained clustering problem in dimension 1 for every norm Lp (p ≥1).
5
Content available remote Modele i metody kolorowania grafów. Część I
Kubale M.
Przegląd Elektrotechniczny
|
2010
|
R. 86, nr 9
115-117
PL
Niniejszy artykuł jest pierwszą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano: (1) co można kolorować w grafie (np. wierzchołki, krawędzie, końcówki, ściany, jednocześnie wierzchołki i krawędzie) oraz (2) jak można kolorować (np. dzielenie kolorów, zawijanie kolorów). Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podajemy oszacowania na liczbę chromatyczną (indeks chromatyczny) oraz podajemy potencjalne zastosowania rozważanych modeli w problemach naukowo-technicznych.
EN
This is the first of a couple of review papers on models and methods of graph coloring. We present herein the main models of graph coloring from a practical point of view. In particular, we show: (1) what elements of a graph can be colored (e.g. vertices, edges, faces, incidences) and (2) how these elements can be colored (e.g. fractional coloring, circular coloring). Since graph coloring is NP-hard in various modifications and variants, we give simple bounds on the chromatic number (chromatic index) as well as we give potential applications of the chromatic methods in science and technology.
6
Content available remote Separating Multi-Color Points on a Plane with Fewest Axis-Parallel Lines
Majumder S., Nandy S.C., Bhattacharya Bhargab.B.
Fundamenta Informaticae
|
2010
|
Vol. 99, nr 3
315-324
EN
In this paper, we deal with the problem of partitioning a set of coplanar points of more than one colors into monochromatic cells using minimum number of axis-parallel straight lines. It is first shown that the problem is NP-hard. A fast heuristic is then presented to solve this problem. Experimental results on randomly generated instances indicate that the proposed method is much faster than the existing techniques, with minor degradation in the cost of the partition.
7
Content available remote On the computational complexity of designing DNA randomizations in a combinatorial protein experiment
Błażewicz J., Dziurdza B., Markiewicz W. T., Oguz C.
Foundations of Computing and Decision Sciences
|
2007
|
Vol. 32, No. 3
185-197
EN
In combinatorial protein experiments based on phage display and similar methods, protein libraries are constructed by expressing a partially randomized DNA (gene) libraries. Since the distribution of proteins in the output library depends on nucleotides frequencies in DNA library one has to adjust them carefully taking into account diversity-completeness trade-off and results from possible previous cycles of experiments (i.e. knowledge about sequences that have been already obtained and tested). The approach considered in this paper allows to maximize the number of new amino acid sequences physically generated in each cycle of the experiment. The mathematical model of the described approach is presented and its computational complexity is analyzed.
8
Content available remote On an NP-hard sorting problem
Giaro K.
Archives of Control Sciences
|
2001
|
Vol. 11, no. 1/2
57-62
EN
We show that the following problem: given a sequence of numbers; arrange these numbers into order using as few interchanges as possible cannot be solved in polynomial time, unless P=NP.
9
Content available remote Models for dependable computation with multiple inputs and some hardness results
Wang Y., Desmedt Y., Burmester M.
Fundamenta Informaticae
|
2000
|
Vol. 42, Nr 1
61-73
EN
We consider the problem of dependable computation with multiple inputs. The goal is to study when redundancy can help to achieve survivability and when it cannot. We use AND/OR graphs to model fault tolerant computations with multiple inputs. While there is a polynomial time algorithm for finding vertex disjoint paths in networks, we will show that the equivalent problem in computation systems with multiple inputs is NP-hard. Our main results are as follows. We present a general model for fault tolerant computation systems with multiple inputs: AND/OR graphs. We show that it is NP-hard to find two vertex disjoint solution graphs in an AND/OR graph. It follows that in the general case redundancy cannot help to achieve survivability, assuming P= NP.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.