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ę "NP-complete" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-7 z 7
    Tytuł:
    More on the Rainbow Disconnection in Graphs
    Autorzy:
    Bai, Xuqing
    Chang, Renying
    Huang, Zhong
    Li, Xueliang
    Powiązania:
    https://bibliotekanauki.pl/articles/32222544.pdf
    Data publikacji:
    2022-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge-coloring
    edge-connectivity
    rainbow disconnection coloring (number)
    Erdős-Gallai type problem
    Nordhaus-Gaddum type bounds
    complexity
    NP-hard (complete)
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1185-1204
    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ł:
    Split Euler Tours In 4-Regular Planar Graphs
    Autorzy:
    Couch, PJ
    Daniel, B.D.
    Guidry, R.
    Paul Wright, W.
    Powiązania:
    https://bibliotekanauki.pl/articles/31341188.pdf
    Data publikacji:
    2016-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    4-regular
    3-connected
    planar
    split Euler tour
    NP-complete
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 1; 23-30
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The Tabu Search approach in coherent co-synthesis of multiprocessors systems
    Autorzy:
    Drabowski, M.
    Czajkowski, K.
    Powiązania:
    https://bibliotekanauki.pl/articles/92834.pdf
    Data publikacji:
    2006
    Wydawca:
    Uniwersytet Przyrodniczo-Humanistyczny w Siedlcach
    Tematy:
    synthesis of system
    coherent
    identification resources
    task scheduling
    NP-complete problem
    heuristic algorithm
    tabu search algorithm
    Opis:
    This paper presents the use of Tabu Search algorithm for solving the problems of coherent synthesis of multiprocessor computer systems. The paper includes a coherent solution of both optimization of partition resources and optimization of tasks scheduling. This publication shows results of computational experiments for different instances of system synthesis problems.
    Źródło:
    Studia Informatica : systems and information technology; 2006, 1(7); 31-45
    1731-2264
    Pojawia się w:
    Studia Informatica : systems and information technology
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The Semitotal Domination Problem in Block Graphs
    Autorzy:
    Henning, Michael A.
    Pal, Saikat
    Pradhan, D.
    Powiązania:
    https://bibliotekanauki.pl/articles/32361741.pdf
    Data publikacji:
    2022-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination
    semitotal domination
    block graphs
    undirected path graphs
    NP-complete
    Opis:
    A set D of vertices in a graph G is a dominating set of G if every vertex outside D is adjacent in G to some vertex in D. A set D of vertices in G is a semitotal dominating set of G if D is a dominating set of G and every vertex in D is within distance 2 from another vertex of D. Given a graph G and a positive integer k, the semitotal domination problem is to decide whether G has a semitotal dominating set of cardinality at most k. The semitotal domination problem is known to be NP-complete for chordal graphs and bipartite graphs as shown in [M.A. Henning and A. Pandey, Algorithmic aspects of semitotal domination in graphs, Theoret. Comput. Sci. 766 (2019) 46–57]. In this paper, we present a linear time algorithm to compute a minimum semitotal dominating set in block graphs. On the other hand, we show that the semitotal domination problem remains NP-complete for undirected path graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 1; 231-248
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The NP-completeness of automorphic colorings
    Autorzy:
    Mazzuoccolo, Giuseppe
    Powiązania:
    https://bibliotekanauki.pl/articles/744108.pdf
    Data publikacji:
    2010
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    NP-complete problems
    chromatic parameters
    graph coloring
    computational complexity
    Opis:
    Given a graph G, an automorphic edge(vertex)-coloring of G is a proper edge(vertex)-coloring such that each automorphism of the graph preserves the coloring. The automorphic chromatic index (number) is the least integer k for which G admits an automorphic edge(vertex)-coloring with k colors. We show that it is NP-complete to determine the automorphic chromatic index and the automorphic chromatic number of an arbitrary graph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2010, 30, 4; 705-710
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The Complexity of Secure Domination Problem in Graphs
    Autorzy:
    Wang, Haichao
    Zhao, Yancai
    Deng, Yunping
    Powiązania:
    https://bibliotekanauki.pl/articles/31342335.pdf
    Data publikacji:
    2018-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    secure domination
    star convex bipartite graph
    doubly chordal graph
    NP-complete
    APX-complete
    Opis:
    A dominating set of a graph G is a subset D ⊆ V (G) such that every vertex not in D is adjacent to at least one vertex in D. A dominating set S of G is called a secure dominating set if each vertex u ∈ V (G) \ S has one neighbor v in S such that (S \ {v}) ∪ {u} is a dominating set of G. The secure domination problem is to determine a minimum secure dominating set of G. In this paper, we first show that the decision version of the secure domination problem is NP-complete for star convex bipartite graphs and doubly chordal graphs. We also prove that the secure domination problem cannot be approximated within a factor of (1−ε) ln |V | for any ε > 0, unless NP⊆DTIME (|V |O(log log |V|)). Finally, we show that the secure domination problem is APX-complete for bounded degree graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 2; 385-396
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-7 z 7

      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