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

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-9 z 9
    Tytuł:
    On the completeness of decomposable properties of graphs
    Autorzy:
    Hałuszczak, Mariusz
    Vateha, Pavol
    Powiązania:
    https://bibliotekanauki.pl/articles/744156.pdf
    Data publikacji:
    1999
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    decomposition
    hereditary property
    completeness
    Opis:
    Let ₁,₂ be additive hereditary properties of graphs. A (₁,₂)-decomposition of a graph G is a partition of E(G) into sets E₁, E₂ such that induced subgraph $G[E_i]$ has the property $_i$, i = 1,2. Let us define a property ₁⊕₂ by {G: G has a (₁,₂)-decomposition}.
    A property D is said to be decomposable if there exists nontrivial additive hereditary properties ₁, ₂ such that D = ₁⊕₂. In this paper we determine the completeness of some decomposable properties and we characterize the decomposable properties of completeness 2.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1999, 19, 2; 229-236
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    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ł:
    Iterated neighborhood graphs
    Autorzy:
    Sonntag, Martin
    Teichert, Hanns-Martin
    Powiązania:
    https://bibliotekanauki.pl/articles/743216.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    neighborhood graph
    2-step graph
    neighborhood completeness number
    Opis:
    The neighborhood graph N(G) of a simple undirected graph G = (V,E) is the graph $(V,E_N)$ where $E_N$ = {{a,b} | a ≠ b, {x,a} ∈ E and {x,b} ∈ E for some x ∈ V}. It is well-known that the neighborhood graph N(G) is connected if and only if the graph G is connected and non-bipartite.
    We present some results concerning the k-iterated neighborhood graph $N^k(G) : = N(N(...N(G)))$ of G. In particular we investigate conditions for G and k such that $N^k(G)$ becomes a complete graph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 3; 403-417
    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 Incidence Coloring of Complete Multipartite and Semicubic Bipartite Graphs
    Autorzy:
    Janczewski, Robert
    Małafiejski, Michał
    Małafiejska, Anna
    Powiązania:
    https://bibliotekanauki.pl/articles/31342434.pdf
    Data publikacji:
    2018-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    incidence coloring
    complete multipartite graphs
    semicubic graphs
    subcubic graphs
    -completeness
    L (1,1)-labelling
    Opis:
    In the paper, we show that the incidence chromatic number $ \chi_i $ of a complete $k$-partite graph is at most $ \Delta + 2 $ (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to $ \Delta + 1 $ if and only if the smallest part has only one vertex (i.e., $ \Delta = n − 1 $). Formally, for a complete k-partite graph $ G = K_{r_1,r_2,...,r_k} $ with the size of the smallest part equal to $ r_1 \ge 1 $ we have $$ \chi_i (G)= \begin{cases} \Delta(G)+1 & \text { if } r_1=1, \\ \Delta(G)+2 & \text { if } r_1>1. \end{cases} $$ In the paper we prove that the incidence 4-coloring problem for semicubic bipartite graphs is \( \mathcal{NP} \)-complete, thus we prove also the \( \mathcal{NP} \)-completeness of L(1, 1)-labeling problem for semicubic bipartite graphs. Moreover, we observe that the incidence 4-coloring problem is \( \mathcal{NP} \)-complete for cubic graphs, which was proved in the paper [12] (in terms of generalized dominating sets).
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 1; 107-119
    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ł:
    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ł
      Wyświetlanie 1-9 z 9

      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