Temat: NP-completeness - Prolib Integro

Skocz do pozycji: 1.

Tytuł:: NP-completeness of weakly convex and convex dominating set decision problems
Autorzy:: Raczek, J.
Tematy:: dominating set
NP-completeness
distance
convex set; Pokaż więcej
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Powiązania:: https://bibliotekanauki.pl/articles/2050778.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 2.

Tytuł:: Balanced problems on graphs with categorization of edges
Autorzy:: Berežný, Štefan
Lacko, Vladimír
Tematy:: algorithms on graphs
categorization of edges
NP-completeness; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/743374.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 3.

Tytuł:: Problems remaining NP-complete for sparse or dense graphs
Autorzy:: Schiermeyer, Ingo
Tematy:: Computational Complexity
NP-Completeness
Hamiltonian Circuit
Hamiltonian Path
Independent Set; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/972006.pdf Link otwiera się w nowym oknie
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'.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 4.

Tytuł:: A Note on Polynomial Algorithm for Cost Coloring of Bipartite Graphs with Δ ≤ 4
Autorzy:: Giaro, Krzysztof
Kubale, Marek
Tematy:: bipartite graph
chromatic sum
cost coloring
NP-completeness
polynomial algorithm; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31526308.pdf Link otwiera się w nowym oknie
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(n²) 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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 5.

Tytuł:: Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Autorzy:: Giaro, Krzysztof
Kubale, Marek
Tematy:: cost coloring
dynamic programming
list coloring
NP-completeness
polynomial-time algorithm; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/744404.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 6.

Tytuł:: The partial visibility representation extension problem
Autorzy:: Liotta, Giuseppe
Gutowski, Grzegorz
Krawczyk, Tomasz
Chaplick, Steven
Guśpiel, Grzegorz
Opis:: For a graph G, a function $\psi$ is called a bar visibility representation of G when for each vertex $\upsilon \in V (G)$, $\psi (\upsilon )$ is a horizontal line segment (bar) and $u \upsilon \in E(G)$ if and only if there is an unobstructed, vertical, $\varepsilon$-wide line of sight between $\psi (u)$ and $\psi (\upsilon )$. Graphs admitting such representations are well understood (via simple characterizations) and recognizable in linear time. For a directed graph G, a bar visibility representation of G, additionally, puts the bar $\psi (u)$ strictly below the bar $\psi (\upsilon )$ for each directed edge (u, v) of G. We study a generalization of the recognition problem where a function $\psi ^{'}$ defined on a subset V' of V(G) is given and the question is whether there is a bar visibility representation $\psi$ of G with $\psi (\upsilon )=\psi ^{'}(\upsilon )$ for every $\upsilon \in$ V'. We show that for undirected graphs this problem, and other closely related problems, is NP-complete, but for certain cases involving directed graphs it is solvable in polynomial time.
Dostawca treści:: Repozytorium Uniwersytetu Jagiellońskiego

Artykuł

na półce

Skocz do pozycji: 7.

Tytuł:: Double dominating sequences in bipartite and co-bipartite graphs
Autorzy:: Sharma, Gopika
Pandey, Arti
Tematy:: double dominating sequences
bipartite graphs
chain graphs
NP-completeness
graph algorithms; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/60274301.pdf Link otwiera się w nowym oknie
Opis:: In a graph $G=(V,E)$, a vertex $u \in V$ dominates a vertex $v \in V$ if $v \in N_G[u]$. A sequence $S=(v_1,v_2, \ldots, v_k)$ of vertices of $G$ is called a double dominating sequence of $G$ if (i) for each $i$, the vertex $v_i$ dominates at least one vertex $u \in V$ which is dominated at most once by the previous vertices of $S$ and, (ii) all vertices of $G$ have been dominated at least twice by the vertices of $S$. Grundy Double Domination problem asks to find a double dominating sequence of maximum length for a given graph $G$. In this paper, we prove that the decision version of the problem is NP-complete for bipartite and co-bipartite graphs. We look for the complexity status of the problem in the class of chain graphs which is a subclass of bipartite graphs. We use dynamic programming approach to solve this problem in chain graphs and propose an algorithm which outputs a Grundy double dominating sequence of a chain graph $G$ in linear-time.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 8.

Tytuł:: On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs
Autorzy:: Hell, Pavol
Hernández-Cruz, César
Tematy:: kernel
3-kernel
NP-completeness
multipartite tournament
cyclically 3-partite digraphs
k-quasi-transitive digraph; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/30147225.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 9.

Tytuł:: Equitable Colorings Of Corona Multiproducts Of Graphs
Autorzy:: Furmánczyk, Hanna
Kubale, Marek
Mkrtchyan, Vahan V.
Tematy:: corona graph
equitable chromatic number
equitable coloring conjecture
equitable graph coloring
multiproduct of graphs
NP-completeness
polynomial algorithm; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31341573.pdf Link otwiera się w nowym oknie
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].
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Skocz do pozycji: 10.

Tytuł:: A note on hardness of multiprocessor scheduling with scheduling solution space tree
Autorzy:: Dwibedy, Debasis
Mohanty, Rakesh
Tematy:: combinatorial structures
computational complexity
hardness
makespan
multiprocessor scheduling
multiuser
NP-completeness
nondeterministic algorithms
reduction
scheduling solution space tree; Pokaż więcej
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Powiązania:: https://bibliotekanauki.pl/articles/27312879.pdf Link otwiera się w nowym oknie
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.
Dostawca treści:: Biblioteka Nauki

Artykuł

na półce

Informacja

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