Informacja

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

Wyszukujesz frazę "NP-Completeness" wg kryterium: Wszystkie pola


Wyświetlanie 1-11 z 11
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ł:
NP-completeness of weakly convex and convex dominating set decision problems
Autorzy:
Raczek, J.
Powiązania:
https://bibliotekanauki.pl/articles/2050778.pdf
Data publikacji:
2004
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
dominating set
NP-completeness
distance
convex set
Opis:
The convex domination number and the weakly convex domination number are new domination parameters. In this paper we show that the decision problems of convex and weakly convex dominating sets are NP-complete for bipartite and split graphs. Using a modified version of Warshall algorithm we can verify in polynomial time whether a given subset of vertices of a graph is convex or weakly convex.
Źródło:
Opuscula Mathematica; 2004, 24, 2; 189-196
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Balanced problems on graphs with categorization of edges
Autorzy:
Berežný, Štefan
Lacko, Vladimír
Powiązania:
https://bibliotekanauki.pl/articles/743374.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
algorithms on graphs
categorization of edges
NP-completeness
Opis:
Suppose a graph G = (V,E) with edge weights w(e) and edges partitioned into disjoint categories S₁,...,Sₚ is given. We consider optimization problems on G defined by a family of feasible sets (G) and the following objective function:
$L₅(D) = max_{1≤i≤p} (max_{e ∈ S_i ∩ D} w(e) - min_{e ∈ S_i ∩ D} w(e))$
For an arbitrary number of categories we show that the L₅-perfect matching, L₅-a-b path, L₅-spanning tree problems and L₅-Hamilton cycle (on a Halin graph) problem are NP-complete.
We also summarize polynomiality results concerning above objective functions for arbitrary and for fixed number of categories.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 1; 5-21
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Problems remaining NP-complete for sparse or dense graphs
Autorzy:
Schiermeyer, Ingo
Powiązania:
https://bibliotekanauki.pl/articles/972006.pdf
Data publikacji:
1995
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Computational Complexity
NP-Completeness
Hamiltonian Circuit
Hamiltonian Path
Independent Set
Opis:
For each fixed pair α,c > 0 let INDEPENDENT SET ($m ≤ cn^α$) and INDEPENDENT SET ($m ≥ (ⁿ₂) - cn^α$) be the problem INDEPENDENT SET restricted to graphs on n vertices with $m ≤ cn^α$ or $m ≥ (ⁿ₂) - cn^α$ edges, respectively. Analogously, HAMILTONIAN CIRCUIT ($m ≤ n + cn^α$) and HAMILTONIAN PATH ($m ≤ n + cn^α$) are the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with $m ≤ n + cn^α$ edges. For each ϵ > 0 let HAMILTONIAN CIRCUIT (m ≥ (1 - ϵ)(ⁿ₂)) and HAMILTONIAN PATH (m ≥ (1 - ϵ)(ⁿ₂)) be the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with m ≥ (1 - ϵ)(ⁿ₂) edges.
We prove that these six restricted problems remain NP-complete. Finally, we consider sufficient conditions for a graph to have a Hamiltonian circuit. These conditions are based on degree sums and neighborhood unions of independent vertices, respectively. Lowering the required bounds the problem HAMILTONIAN CIRCUIT jumps from 'easy' to 'NP-complete'.
Źródło:
Discussiones Mathematicae Graph Theory; 1995, 15, 1; 33-41
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ł:
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Autorzy:
Giaro, Krzysztof
Kubale, Marek
Powiązania:
https://bibliotekanauki.pl/articles/744404.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cost coloring
dynamic programming
list coloring
NP-completeness
polynomial-time algorithm
Opis:
We consider a list cost coloring of vertices and edges in the model of vertex, edge, total and pseudototal coloring of graphs. We use a dynamic programming approach to derive polynomial-time algorithms for solving the above problems for trees. Then we generalize this approach to arbitrary graphs with bounded cyclomatic numbers and to their multicolorings.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 2; 361-376
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs
Autorzy:
Hell, Pavol
Hernández-Cruz, César
Powiązania:
https://bibliotekanauki.pl/articles/30147225.pdf
Data publikacji:
2014-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
kernel
3-kernel
NP-completeness
multipartite tournament
cyclically 3-partite digraphs
k-quasi-transitive digraph
Opis:
Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V (D) − N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V (D). A 2-kernel is called a kernel. It is known that the problem of determining whether a digraph has a kernel (“the kernel problem”) is NP-complete, even in quite restricted families of digraphs. In this paper we analyze the computational complexity of the corresponding 3-kernel problem, restricted to three natural families of digraphs. As a consequence of one of our main results we prove that the kernel problem remains NP-complete when restricted to 3-colorable digraphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 1; 167-185
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on hardness of multiprocessor scheduling with scheduling solution space tree
Autorzy:
Dwibedy, Debasis
Mohanty, Rakesh
Powiązania:
https://bibliotekanauki.pl/articles/27312879.pdf
Data publikacji:
2023
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
combinatorial structures
computational complexity
hardness
makespan
multiprocessor scheduling
multiuser
NP-completeness
nondeterministic algorithms
reduction
scheduling solution space tree
Opis:
We study the hardness of the non-preemptive scheduling problem of a list of independent jobs on a set of identical parallel processors with a makespan minimization objective. We make a maiden attempt to explore the combinatorial structure of the problem by introducing a scheduling solution space tree (SSST) as a novel data structure. We formally define and characterize the properties of SSST through our analytical results. We show that the multiprocessor scheduling problem is N P-complete with an alternative technique using SSST and weighted scheduling solution space tree (WSSST) data structures. We propose a non-deterministic polynomial-time algorithm called magic scheduling (MS) based on the reduction framework. We also define a new variant of multiprocessor scheduling by including the user as an additional input parameter, which we called the multiuser multiprocessor scheduling problem (MUMPSP). We also show that MUMPSP is N P-complete. We conclude the article by exploring several non-trivial research challenges for future research investigations.
Źródło:
Computer Science; 2023, 24 (1); 53--74
1508-2806
2300-7036
Pojawia się w:
Computer Science
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ł:
The smallest hard-to-color graphs for the classical, total and strong colorings of vertices
Autorzy:
Kubale, M.
Manuszewski, K.
Powiązania:
https://bibliotekanauki.pl/articles/206254.pdf
Data publikacji:
1999
Wydawca:
Polska Akademia Nauk. Instytut Badań Systemowych PAN
Tematy:
optymalizacja
teoria grafów
złożoność obliczeniowa
benchmark
chromatic number
chromatic sum
graph oring
hard-to-color graph
NP-completeness
strong coloring
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.
Źródło:
Control and Cybernetics; 1999, 28, 2; 355-365
0324-8569
Pojawia się w:
Control and Cybernetics
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Towards the boundary between easy and hard control problems in multicast Clos networks
Autorzy:
Obszarski, P.
Jastrzębski, A.
Kubale, M.
Powiązania:
https://bibliotekanauki.pl/articles/200819.pdf
Data publikacji:
2015
Wydawca:
Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:
Clos-network
2-cast call
hypergraph edge coloring
rearrageable network
nonblocking network
NP-completeness
3-uniform hypergraph
sieci
połączenie sieciowe
problem sieciowy
Opis:
In this article we study 3-stage Clos networks with multicast calls in general and 2-cast calls, in particular. We investigate various sizes of input and output switches and discuss some routing problems involved in blocking states. To express our results in a formal way we introduce a model of hypergraph edge-coloring. A new class of bipartite hypergraphs corresponding to Clos networks is studied. We identify some polynomially solvable instances as well as a number of NP-complete cases. Our results warn of possible troubles arising in the control of Clos networks even if they are composed of small-size switches in outer stages. This is in sharp contrast to classical unicast Clos networks for which all the control problems are polynomially solvable.
Źródło:
Bulletin of the Polish Academy of Sciences. Technical Sciences; 2015, 63, 3; 739-744
0239-7528
Pojawia się w:
Bulletin of the Polish Academy of Sciences. Technical Sciences
Dostawca treści:
Biblioteka Nauki
Artykuł
    Wyświetlanie 1-11 z 11

    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