Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "Polynomial" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-8 z 8
    Tytuł:
    An attractive class of bipartite graphs
    Autorzy:
    Boliac, Rodica
    Lozin, Vadim
    Powiązania:
    https://bibliotekanauki.pl/articles/743515.pdf
    Data publikacji:
    2001
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    bipartite graphs
    structural characterization
    polynomial algorithm
    Opis:
    In this paper we propose a structural characterization for a class of bipartite graphs defined by two forbidden induced subgraphs. We show that the obtained characterization leads to polynomial-time algorithms for several problems that are NP-hard in general bipartite graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2001, 21, 2; 293-301
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines. Computational Experiments
    Autorzy:
    Duraj, S.
    Kopeć, P.
    Kubale, M.
    Pikies, T.
    Powiązania:
    https://bibliotekanauki.pl/articles/376001.pdf
    Data publikacji:
    2017
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    batch scheduling
    bipartite graph
    polynomial algorithm
    uniform machines
    Opis:
    In this paper, we consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard, we show that our problem can be solved to optimality in polynomial time under some restrictions imposed on the number of machines, their speeds, and the structure of the incompatibility graph. The theoretical considerations are accompanied by computer experiments with a certain model of scheduling.
    Źródło:
    Decision Making in Manufacturing and Services; 2017, 11, 1-2; 53-61
    1896-8325
    2300-7087
    Pojawia się w:
    Decision Making in Manufacturing and Services
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Persistency in the Traveling Salesman Problem on Halin graphs
    Autorzy:
    Lacko, Vladimír
    Powiązania:
    https://bibliotekanauki.pl/articles/743793.pdf
    Data publikacji:
    2000
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    persistency
    traveling salesman problem
    Halin graph
    polynomial algorithm
    Opis:
    For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition $E_{All}$, $E_{Some}$, $E_{None}$ of the edge set E, where:
    $E_{All}$ = {e ∈ E, e belongs to all optimum solutions},
    $E_{None}$ = {e ∈ E, e does not belong to any optimum solution} and
    $E_{Some}$ = {e ∈ E, e belongs to some but not to all optimum solutions}.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2000, 20, 2; 231-242
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A Note on Polynomial Algorithm for Cost Coloring of Bipartite Graphs with Δ ≤ 4
    Autorzy:
    Giaro, Krzysztof
    Kubale, Marek
    Powiązania:
    https://bibliotekanauki.pl/articles/31526308.pdf
    Data publikacji:
    2020-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    bipartite graph
    chromatic sum
    cost coloring
    NP-completeness
    polynomial algorithm
    Opis:
    In the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree Δ ≤ 4 can be solved in O(n2) time. This extends Jansen’s result [K. Jansen, The optimum cost chromatic partition problem, in: Proc. CIAC’97, Lecture Notes in Comput. Sci. 1203 (1997) 25–36] for paths and cycles to subgraphs of biquartic graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 3; 885-891
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Spanning trees with many or few colors in edge-colored graphs
    Autorzy:
    Broersma, Hajo
    Li, Xueliang
    Powiązania:
    https://bibliotekanauki.pl/articles/971955.pdf
    Data publikacji:
    1997
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge-coloring
    spanning tree
    matroid (intersection)
    complexity
    NP-complete
    NP-hard
    polynomial algorithm
    (minimum) dominating set
    Opis:
    Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1997, 17, 2; 259-269
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
    Autorzy:
    Furmańczyk, H.
    Kubale, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/200295.pdf
    Data publikacji:
    2017
    Wydawca:
    Polska Akademia Nauk. Czytelnia Czasopism PAN
    Tematy:
    equitable coloring
    NP-hardness
    polynomial algorithm
    scheduling
    uniform machine
    kolorowanie grafów
    twardość NP
    algorytm wielomianowy
    planowanie
    Opis:
    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.
    Źródło:
    Bulletin of the Polish Academy of Sciences. Technical Sciences; 2017, 65, 1; 29-34
    0239-7528
    Pojawia się w:
    Bulletin of the Polish Academy of Sciences. Technical Sciences
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Equitable Colorings Of Corona Multiproducts Of Graphs
    Autorzy:
    Furmánczyk, Hanna
    Kubale, Marek
    Mkrtchyan, Vahan V.
    Powiązania:
    https://bibliotekanauki.pl/articles/31341573.pdf
    Data publikacji:
    2017-11-27
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    corona graph
    equitable chromatic number
    equitable coloring conjecture
    equitable graph coloring
    multiproduct of graphs
    NP-completeness
    polynomial algorithm
    Opis:
    A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by χ=(G). It is known that the problem of computation of χ=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts of graphs. In particular, we obtain some results regarding the equitable chromatic number for the l-corona product G ◦l H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs are mostly constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G. Moreover, we confirm the Equitable Coloring Conjecture for corona products of such graphs. This paper extends the results from [H. Furmánczyk, K. Kaliraj, M. Kubale and V.J. Vivin, Equitable coloring of corona products of graphs, Adv. Appl. Discrete Math. 11 (2013) 103–120].
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 4; 1079-1094
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Better polynomial algorithms for scheduling unit-length jobswith bipartite incompatibility graphs on uniform machines
    Autorzy:
    Pikies, T.
    Kubale, Marek
    Powiązania:
    https://bibliotekanauki.pl/articles/201958.pdf
    Data publikacji:
    2019
    Wydawca:
    Polska Akademia Nauk. Czytelnia Czasopism PAN
    Tematy:
    approximation algorithm
    graph coloring
    incompatible job
    polynomial algorithm
    scheduling
    uniform machine
    unit-time jobs
    algorytm aproksymacyjny
    kolorowanie grafów
    algorytm wielomianowy
    planowanie
    praca jednostkowa
    Opis:
    The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qm|pj = 1, G = bisubquartic|Cmax. The second one is Algorithm 3 which is 4-approximate for the problem Qm|pj = 1, G = bisubquartic|ΣCj, where m ϵ {2, 3, 4}. The theory behind the proposed algorithms is based on the properties of 2-coloring with maximal coloring width, and on the properties of ideal machine, an abstract machine that we introduce in this paper.
    Źródło:
    Bulletin of the Polish Academy of Sciences. Technical Sciences; 2019, 67, 1; 31-36
    0239-7528
    Pojawia się w:
    Bulletin of the Polish Academy of Sciences. Technical Sciences
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-8 z 8

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies