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 Pedagogiczna Biblioteka Wojewódzka im. Komisji Edukacji Narodowej w Lublinie Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaPedagogiczna Biblioteka Wojewódzka im. Komisji Edukacji Narodowej w Lublinie
Zmień bibliotekę

Wyszukujesz frazę "NP-hard" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-8 z 8
    Tytuł:
    Spanning trees with many or few colors in edge-colored graphs
    Autorzy:
    Broersma, Hajo
    Li, Xueliang
    Tematy:
    edge-coloring
    spanning tree
    matroid (intersection)
    complexity
    NP-complete
    NP-hard
    polynomial algorithm
    (minimum) dominating set
    Pokaż więcej
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Powiązania:
    https://bibliotekanauki.pl/articles/971955.pdf  Link otwiera się w nowym oknie
    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.
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the Complexity of Reinforcement in Graphs
    Autorzy:
    Rad, Nader Jafari
    Tematy:
    domination
    total domination
    total restrained domination
    p- domination
    k-rainbow domination
    reinforcement
    NP-hard
    Pokaż więcej
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Powiązania:
    https://bibliotekanauki.pl/articles/31340751.pdf  Link otwiera się w nowym oknie
    Opis:
    We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Algorithms for the subset sum problem
    Algorytmy dla problemu sumy podzbioru
    Autorzy:
    Judasz, Szymon
    Opis:
    One of the discussed problems by R. Karp was subset sum problem. More efficient algorithms have been developed since then. I will describe choosen algorithms and compare them. It turns out that the theoretically fastest algoritm performs slowly.
    Jednym z rozważanych przez R. Karpa problemów był problem sumy podzbioru. Od tamtych czasów powstały nowe algorytmy o lepszych parametrach. W pracy opisuję i porównuję wybrane algorytmy rozwiązujące problem sumy podzbioru. Okazuje się, że teoretycznie najszybszy algorytm w warunkach praktycznych działa wolno.
    Dostawca treści:
    Repozytorium Uniwersytetu Jagiellońskiego
    Inne
    Tytuł:
    More on the Rainbow Disconnection in Graphs
    Autorzy:
    Bai, Xuqing
    Chang, Renying
    Huang, Zhong
    Li, Xueliang
    Tematy:
    edge-coloring
    edge-connectivity
    rainbow disconnection coloring (number)
    Erdős-Gallai type problem
    Nordhaus-Gaddum type bounds
    complexity
    NP-hard (complete)
    Pokaż więcej
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Powiązania:
    https://bibliotekanauki.pl/articles/32222544.pdf  Link otwiera się w nowym oknie
    Opis:
    Let G be a nontrivial edge-colored connected graph. An edge-cut R of G is called a rainbow-cut if no two of its edges are colored the same. An edge-colored graph G is rainbow disconnected if for every two vertices u and v of G, there exists a u-v-rainbow-cut separating them. For a connected graph G, the rainbow disconnection number of G, denoted by rd(G), is defined as the smallest number of colors that are needed in order to make G rainbow disconnected. In this paper, we first determine the maximum size of a connected graph G of order n with rd(G) = k for any given integers k and n with 1 ≤ k ≤ n − 1, which solves a conjecture posed only for n odd in [G. Chartrand, S. Devereaux, T.W. Haynes, S.T. Hedetniemi and P. Zhang, Rainbow disconnection in graphs, Discuss. Math. Graph Theory 38 (2018) 1007–1021]. From this result and a result in their paper, we obtain Erdős-Gallai type results for rd(G). Secondly, we discuss bounds on rd(G) for complete multipartite graphs, critical graphs with respect to the chromatic number, minimal graphs with respect to the chromatic index, and regular graphs, and we also give the values of rd(G) for several special graphs. Thirdly, we get Nordhaus-Gaddum type bounds for rd(G), and examples are given to show that the upper and lower bounds are sharp. Finally, we show that for a connected graph G, to compute rd(G) is NP-hard. In particular, we show that it is already NP-complete to decide if rd(G) = 3 for a connected cubic graph. Moreover, we show that for a given edge-colored (with an unbounded number of colors) connected graph G it is NP-complete to decide whether G is rainbow disconnected.
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Binary neural networks for N-queens problems and their VLSI implementations
    Autorzy:
    Funabiki, N.
    Kurokawa, T.
    Ohta, M.
    Tematy:
    algorytm
    binarna sieć neuronowa
    N-queens problem
    optymalizacja kombinatoryczna
    problem n-hetmanów
    projekt VLSI
    binary neural network
    combinatorial optimization
    NP-hard
    VLSI design
    algorithm
    Pokaż więcej
    Wydawca:
    Polska Akademia Nauk. Instytut Badań Systemowych PAN
    Powiązania:
    https://bibliotekanauki.pl/articles/205704.pdf  Link otwiera się w nowym oknie
    Opis:
    Combinatorial optimization problems compose an important class of matliematical problems that include a variety of practical applications, such as VLSI design automation, communication network design and control, job scheduling, games, and genome informatics. These problems usually have a large number of variables to be solved. For example, problems for VLSI design automation require several million variables. Besides, thieir computational complexity is often intractable due to NP-hardness. Neural networks have provided elegant solutions as approximation algorithms to these hard problems due to their natural parallelism and their affinity to hardware realization. Particularly, binary neural networks have great potential to conform to current digital VLSI design technology, because any state and parameter in binary neural networks are expressed in a discrete fashion. This paper presents our studies on binary neural networks to the N-queens problem, and the three different approaches to VLSI implementations focusing on the efficient realization of the synaptic connection networks. Reconfigurable devices such as CPLDs and FPGAs contribute the realization of a scalable architecture with the ultra high speed of computation. Based on the proposed architecture, more than several thousands of binary neurons can be realized on one FPGA chip.
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Wielopoziomowe ograniczone minimalne drzewo rozpinające
    Multi-level Capacitated Minimum Spanning Tree.
    Autorzy:
    Bartodziej, Filip
    Opis:
    Problem Multi-level Capacitated Minimum Spanning Tree (MLCMST) jest sieciowym problemem, który wyłonił się na początku 21go wieku i wzbudził dość duże zainteresowanie w ciągu ostatnich 20tu lat. Ten problem jest generalizacją innego problemu sieciowego, Capacitated Minimum Spanning Tree (CMST), i ma na celu modelować wyzwania napotykane w nowoczesnym projektowaniu sieci. Ta praca ma na celu zebranie i klasyfikacje heurystyk i matematycznych programów używanych do rozwiązywania problemu MLCMST. Przedstawia ona także programistyczny projekt zawierający implementację heurystyk i programów liniowych. Projekt ten ma ułatwić eksperymentację z nowymi pomysłami próbującymi rozwiązać problem MLCMST.
    The Multi-level Capacitated Minimum Spanning Tree (MLCMST) problem is a network problem that emerged at the beginning of the $21^{th}$ century and has garnered a considerable attention in the last 20 years. This problem is a generalization of another network problem, Capacitated Minimum Spanning Tree (CMST), and aims to capture challenges encountered in modern network design. This paper is intended to gather and classify heuristics and mathematical programming formulations used in tackling the Multi-level Capacitated Minimum Spanning Tree problem. It also introduces a C++ framework, containing implementations of heuristics and linear programs, with purpose of providing a foothold for experimenting with new approaches to tackling MLCMST problem.
    Dostawca treści:
    Repozytorium Uniwersytetu Jagiellońskiego
    Inne
    Tytuł:
    The smallest hard-to-color graphs for the classical, total and strong colorings of vertices
    Autorzy:
    Kubale, M.
    Manuszewski, K.
    Tematy:
    optymalizacja
    teoria grafów
    złożoność obliczeniowa
    benchmark
    chromatic number
    chromatic sum
    graph oring
    hard-to-color graph
    NP-completeness
    strong coloring
    Pokaż więcej
    Wydawca:
    Polska Akademia Nauk. Instytut Badań Systemowych PAN
    Powiązania:
    https://bibliotekanauki.pl/articles/206254.pdf  Link otwiera się w nowym oknie
    Opis:
    : Let A(G) be the number of colors used by algorithm to color the vertices of graph G. A graph G is said to be hard-to-color (HC) (resp. slightly HC) if for every (resp. some) implementation of the algorithm A we have A(G) > chi(G), where chi(G) is the chromatic number of G. The study of HC graphs makes it possible design improved algorithms trying to avoid hard instances as far possible. Hard-to-color graphs are also good benchmarks for the evaluation of existing and future algorithms and provide an alternative way of assessing their quality. In this paper we demonstrate the smallest HC graphs for the best known coloring heuristics in classical applications, as well as when adapted to the chromatic sum coloring and strong coloring of vertices.
    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