Filters
total: 86
Best results in : Research Potential Pokaż wszystkie wyniki (69)
Search results for: SEMI-EQUITABLE COLORING
-
Zespół Algorytmów i Modelowania Systemów
Research PotentialStudiowanie problemów i modeli teoriografowych ma na celu badanie złożoności obliczeniowej uogólnień problemu klasycznego kolorowania wierzchołków i krawędzi grafu znajdujących zastosowania w modelowaniu praktycznych problemów oraz badanie nowych miar oceny skuteczności algorytmów. W zakresie szeregowania zadań badania koncentrują się na konstrukcji harmonogramów optymalnych z punktu widzenia długości harmonogramu i średniego czasu...
-
Katedra Chemii Analitycznej
Research PotentialZespół naukowo-badawczy z Katedry Chemii Analitycznej prowadzi badania podstawowe w zakresie: -opracowania nowych procedur analitycznych przeznaczonych do wykrywania, identyfikacji oraz oznaczenia szerokiego spectrum analitów w próbkach różnego typu materiałów charakteryzujących się złożonym a często także zmiennym składem matrycy, -budowy i badań charakterystyki analitycznej nowych typów elektronicznych nosów, -oszacowania wpływu...
-
Zespół Systemów i Urządzeń Energetyki Cieplnej
Research Potentialintensyfikacja wymiany ciepła, nowoczesne wymienniki ciepła, wysokotemperaturowe pompy ciepła, mikrosiłownie ORC i inne
Best results in : Business Offer Pokaż wszystkie wyniki (17)
Search results for: SEMI-EQUITABLE COLORING
-
Laboratorium Maszyn i Systemów Okrętowych
Business OfferBadania procesów i zjawisk w czasie realizacji obiegu roboczego w silniku z zapłonem samoczynnym dla potrzeb diagnostyki maszyn tłokowych.
-
Laboratorium Diagnostyki Silników i Sprężarek Tłokowych
Business OfferIdentyfikacja stanu technicznego głównych układów funkcjonalnych silników spalinowych i sprężarek w oparciu o wyniki badań diagnostycznych.
-
Laboratorium Badań Drogowych
Business Offer
Other results Pokaż wszystkie wyniki (464)
Search results for: SEMI-EQUITABLE COLORING
-
Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
PublicationIn the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP- complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize...
-
Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling
Publication -
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationWe consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.
-
Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationIn this paper we consider the complexity of semi-equitable k-coloring of the vertices of a cubic or subcubic graph. We show that, given n-vertex subcubic graph G, a semi-equitable k-coloring of G is NP-hard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring.
-
Equitable coloring of hypergraphs
PublicationA hypergraph is equitablyk-colorable if its vertices can be partitioned into k sets/colorclasses in such a way that monochromatic edges are avoided and the number of verticesin any two color classes differs by at most one. We prove that the problem of equitable 2-coloring of hypergraphs is NP-complete even for 3-uniform hyperstars. Finally, we apply the method of dynamic programming for designing a polynomial-time algorithm to...