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

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-13 z 13
    Tytuł:
    2-placement of (p,q)-trees
    Autorzy:
    Orchel, Beata
    Powiązania:
    https://bibliotekanauki.pl/articles/743376.pdf
    Data publikacji:
    2003
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    tree
    bipartite graph
    packing graph
    Opis:
    Let G = (L,R;E) be a bipartite graph such that V(G) = L∪R, |L| = p and |R| = q. G is called (p,q)-tree if G is connected and |E(G)| = p+q-1.
    Let G = (L,R;E) and H = (L',R';E') be two (p,q)-tree. A bijection f:L ∪ R → L' ∪ R' is said to be a biplacement of G and H if f(L) = L' and f(x)f(y) ∉ E' for every edge xy of G. A biplacement of G and its copy is called 2-placement of G. A bipartite graph G is 2-placeable if G has a 2-placement. In this paper we give all (p,q)-trees which are not 2-placeable.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2003, 23, 1; 23-36
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    2-biplacement without fixed points of (p, q)-bipartite graphs
    Autorzy:
    Orchel, B.
    Powiązania:
    https://bibliotekanauki.pl/articles/255209.pdf
    Data publikacji:
    2005
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    bipartite graph
    packing
    embedding
    Opis:
    In this paper we consider 2-biplacement without fixed points of paths and (p, q)--bipartite graphs of small size. We give all (p, q)-bipartite graphs G of size q for which the set S*(G) of all 2-biplacements of G without fixed points is empty.
    Źródło:
    Opuscula Mathematica; 2005, 25, 2; 269-274
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Placing bipartite graphs of small size II
    Autorzy:
    Orchel, Beata
    Powiązania:
    https://bibliotekanauki.pl/articles/972020.pdf
    Data publikacji:
    1996
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    packing of graphs
    bipartite graph
    Opis:
    In this paper we give all pairs of non mutually placeable (p,q)-bipartite graphs G and H such that 2 ≤ p ≤ q, e(H) ≤ p and e(G)+e(H) ≤ 2p+q-1.
    Źródło:
    Discussiones Mathematicae Graph Theory; 1996, 16, 2; 93-110
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Graphs that are Critical for the Packing Chromatic Number
    Autorzy:
    Brešar, Boštjan
    Ferme, Jasmina
    Powiązania:
    https://bibliotekanauki.pl/articles/32318620.pdf
    Data publikacji:
    2022-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    packing coloring
    critical graph
    diameter
    block graph
    tree
    Opis:
    Given a graph G, a coloring c : V (G) → {1, …, k} such that c(u) = c(v) = i implies that vertices u and v are at distance greater than i, is called a packing coloring of G. The minimum number of colors in a packing coloring of G is called the packing chromatic number of G, and is denoted by χρ(G). In this paper, we propose the study of χρ-critical graphs, which are the graphs G such that for any proper subgraph H of G, χρ(H) < χρ(G). We characterize χρ-critical graphs with diameter 2, and χρ-critical block graphs with diameter 3. Furthermore, we characterize χρ-critical graphs with small packing chromatic number, and we also consider χρ-critical trees. In addition, we prove that for any graph G and every edge e ∈ E(G), we have (χρ(G)+1)/2 ≤ χρ(G−e) ≤ χρ(G), and provide a corresponding realization result, which shows that χρ(G − e) can achieve any of the integers between these bounds.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 2; 569-589
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Packing Coloring of Some Undirected and Oriented Coronae Graphs
    Autorzy:
    Laïche, Daouya
    Bouchemakh, Isma
    Sopena, Éric
    Powiązania:
    https://bibliotekanauki.pl/articles/31341695.pdf
    Data publikacji:
    2017-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    packing coloring
    packing chromatic number
    corona graph
    path
    cycle
    Opis:
    The packing chromatic number χρ(G) of a graph G is the smallest integer k such that its set of vertices V(G) can be partitioned into k disjoint subsets V1, . . ., Vk, in such a way that every two distinct vertices in Vi are at distance greater than i in G for every i, 1 ≤ i ≤ k. For a given integer p ≥ 1, the p-corona of a graph G is the graph obtained from G by adding p degree-one neighbors to every vertex of G. In this paper, we determine the packing chromatic number of p-coronae of paths and cycles for every p ≥ 1. Moreover, by considering digraphs and the (weak) directed distance between vertices, we get a natural extension of the notion of packing coloring to digraphs. We then determine the packing chromatic number of orientations of p-coronae of paths and cycles.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 3; 665-690
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The s-packing chromatic number of a graph
    Autorzy:
    Goddard, Wayne
    Xu, Honghai
    Powiązania:
    https://bibliotekanauki.pl/articles/743305.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph
    coloring
    packing
    broadcast chromatic number
    Opis:
    Let S = (a₁, a₂, ...) be an infinite nondecreasing sequence of positive integers. An S-packing k-coloring of a graph G is a mapping from V(G) to {1,2,...,k} such that vertices with color i have pairwise distance greater than $a_i$, and the S-packing chromatic number $χ_S(G)$ of G is the smallest integer k such that G has an S-packing k-coloring. This concept generalizes the concept of proper coloring (when S = (1,1,1,...)) and broadcast coloring (when S = (1,2,3,4,...)). In this paper, we consider bounds on the parameter and its relationship with other parameters. We characterize the graphs with $χ_S = 2$ and determine $χ_S$ for several common families of graphs. We examine $χ_S$ for the infinite path and give some exact values and asymptotic bounds. Finally we consider complexity questions, especially about recognizing graphs with $χ_S = 3$.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 4; 795-806
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A Survey on Packing Colorings
    Autorzy:
    Brešar, Boštjan
    Ferme, Jasmina
    Klavžar, Sandi
    Rall, Douglas F.
    Powiązania:
    https://bibliotekanauki.pl/articles/31804166.pdf
    Data publikacji:
    2020-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    packing coloring
    packing chromatic number
    subcubic graph
    S -packing chromatic number
    computational complexity
    Opis:
    If S = (a1, a2, . . .) is a non-decreasing sequence of positive integers, then an S-packing coloring of a graph G is a partition of V (G) into sets X1, X2, . . . such that for each pair of distinct vertices in the set Xi, the distance between them is larger than ai. If there exists an integer k such that V (G) = X1 ∪ ∪ Xk, then the partition is called an S-packing k-coloring. The S-packing chromatic number of G is the smallest k such that G admits an S-packing k-coloring. If ai = i for every i, then the terminology reduces to packing colorings and packing chromatic number. Since the introduction of these generalizations of the chromatic number in 2008 more than fifty papers followed. Here we survey the state of the art on the packing coloring, and its generalization, the S-packing coloring. We also list several conjectures and open problems.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 4; 923-970
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    3-biplacement of bipartite graphs
    Autorzy:
    Adamus, L.
    Leśniak, E.
    Orchel, B.
    Powiązania:
    https://bibliotekanauki.pl/articles/255067.pdf
    Data publikacji:
    2008
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    bipartite graph
    packing of graphs
    placement
    biplacement
    Opis:
    Let G = (L,R;E) be a bipartite graph with color classes L and R and edge set E. A set of two bijections {φ1, φ2}, φ1, φ2 : L ∪ R → L ∪ R, is said to be a 3-biplacement of G if [formula], where φ*/1, φ*/2 are the maps defined on E, induced by φ1, φ2, respectively. We prove that if ‌L‌ = p, ‌R‌ = q, 3 ≤ p ≤ q, then every graph G = (L, R; E) of size at most p has a 3-biplacement.
    Źródło:
    Opuscula Mathematica; 2008, 28, 3; 223-231
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Packing Trees in Complete Bipartite Graphs
    Autorzy:
    Wang, Jieyan
    Powiązania:
    https://bibliotekanauki.pl/articles/32361740.pdf
    Data publikacji:
    2022-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    packing
    placement
    edge-disjoint tree
    bipartite graph
    Opis:
    An embedding of a graph H in a graph G is an injection (i.e., a one-to-one function) σ from the vertices of H to the vertices of G such that σ(x)σ(y) is an edge of G for all edges xy of H. The image of H in G under σ is denoted by σ(H). A k-packing of a graph H in a graph G is a sequence (σ1, σ2,…, σk) of embeddings of H in G such that σ1(H), σ2(H),…, σk(H) are edge disjoint. We prove that for any tree T of order n, there is a 4-packing of T in a complete bipartite graph of order at most n+12.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 1; 263-275
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Maximum Cycle Packing in Eulerian Graphs Using Local Traces
    Autorzy:
    Recht, Peter
    Sprengel, Eva-Maria
    Powiązania:
    https://bibliotekanauki.pl/articles/31339129.pdf
    Data publikacji:
    2015-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge-disjoint cycle packing
    local traces
    extremal problems in graph theory
    Opis:
    For a graph G = (V,E) and a vertex v ∈ V, let T(v) be a local trace at v, i.e. T(v) is an Eulerian subgraph of G such that every walk W(v), with start vertex v can be extended to an Eulerian tour in T(v). We prove that every maximum edge-disjoint cycle packing Z* of G induces a maximum trace T(v) at v for every v ∈ V. Moreover, if G is Eulerian then sufficient conditions are given that guarantee that the sets of cycles inducing maximum local traces of G also induce a maximum cycle packing of G.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 1; 121-132
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A genetic algorithm for the maximum 2-packing set problem
    Autorzy:
    Trejo-Sánchez, Joel Antonio
    Fajardo-Delgado, Daniel
    Gutierrez-Garcia, J. Octavio
    Powiązania:
    https://bibliotekanauki.pl/articles/330154.pdf
    Data publikacji:
    2020
    Wydawca:
    Uniwersytet Zielonogórski. Oficyna Wydawnicza
    Tematy:
    maximum 2-packing set
    genetic algorithms
    graph algorithms
    algorytm genetyczny
    algorytm grafowy
    Opis:
    Given an undirected connected graph G = (V, E), a subset of vertices S is a maximum 2-packing set if the number of edges in the shortest path between any pair of vertices in S is at least 3 and S has the maximum cardinality. In this paper, we present a genetic algorithm for the maximum 2-packing set problem on arbitrary graphs, which is an NP-hard problem. To the best of our knowledge, this work is a pioneering effort to tackle this problem for arbitrary graphs. For comparison, we extended and outperformed a well-known genetic algorithm originally designed for the maximum independent set problem. We also compared our genetic algorithm with a polynomial-time one for the maximum 2-packing set problem on cactus graphs. Empirical results show that our genetic algorithm is capable of finding 2-packing sets with a cardinality relatively close (or equal) to that of the maximum 2-packing sets. Moreover, the cardinality of the 2-packing sets found by our genetic algorithm increases linearly with the number of vertices and with a larger population and a larger number of generations. Furthermore, we provide a theoretical proof demonstrating that our genetic algorithm increases the fitness for each candidate solution when certain conditions are met.
    Źródło:
    International Journal of Applied Mathematics and Computer Science; 2020, 30, 1; 173-184
    1641-876X
    2083-8492
    Pojawia się w:
    International Journal of Applied Mathematics and Computer Science
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Some properties of the zero divisor graph of a commutative ring
    Autorzy:
    Nazzal, Khalida
    Ghanem, Manal
    Powiązania:
    https://bibliotekanauki.pl/articles/729189.pdf
    Data publikacji:
    2014
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    automorphism group of a graph
    center of a graph
    core of a graph
    k-domination number
    Gaussian integers modulo n
    median of a graph
    2-packing
    perfect graph
    and zero divisor graph
    Opis:
    Let Γ(R) be the zero divisor graph for a commutative ring with identity. The k-domination number and the 2-packing number of Γ(R), where R is an Artinian ring, are computed. k-dominating sets and 2-packing sets for the zero divisor graph of the ring of Gaussian integers modulo n, Γ(ℤₙ[i]), are constructed. The center, the median, the core, as well as the automorphism group of Γ(ℤₙ[i]) are determined. Perfect zero divisor graphs Γ(R) are investigated.
    Źródło:
    Discussiones Mathematicae - General Algebra and Applications; 2014, 34, 2; 167-181
    1509-9415
    Pojawia się w:
    Discussiones Mathematicae - General Algebra and Applications
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Resource Utilization Estimation and Core Placement in an NoC-based MPSoC realizing a data-dominated algorithm
    Szacowanie wykorzystania zasobów i rozmieszczenia rdzeni przy realizacji algorytmów zdominowanych danymi w MPSoC opartych na NoC
    Autorzy:
    Dondziak, P.
    Dziurzański, P.
    Powiązania:
    https://bibliotekanauki.pl/articles/154795.pdf
    Data publikacji:
    2010
    Wydawca:
    Stowarzyszenie Inżynierów i Techników Mechaników Polskich
    Tematy:
    szacowanie zasobów
    odwzorowanie rdzeni
    diagram przepływu danych i kontroli
    problem pokrycia paska
    sieci wewnątrzukładowe
    resource estimation
    core mapping
    Control Data Flow Graph
    Rectangular Strip Packing Problem
    Network on Chip (NoC)
    Opis:
    In this paper we propose a technique for estimating the number of NoC-based MPSoCs resources (measured in FPGA LUTs) needed for realizing an arbitrary data-dominated algorithm given in the SystemC language. This technique utilizes Control Data Flow Graphs describing the functionality of the code. In order to map the cores into the target chip we use the Bottom-Left-Decreasing algorithm for solving the 2D Rectangular Strip Packing problem. We illustrate the proposed technique with a lossless audio FLAC codec.
    W artykule zaproponowano technikę szacowania zasobów potrzebnych do realizacji wielordzeniowych układów MPSoC opartych na sieciach wewnątrzukładowych NoC (ang. Networks on Chip) realizujących dowolny algorytm zdominowany danymi. Algorytm ten jest wyrażony za pomocą kodu w języku opisu systemu SystemC. Jako miarę powierzchni przyjęto liczbę tablic look-up-table (LUT) układów typu FPGA, do których wejściowe algorytmy zostają odwzorowywane. Proponowana technika wykorzystuje diagram przepływu danych i kontroli (ang. Control Data Flow Graph, CDFG), opisujący funkcjonalność kodu. Następnie dla węzłów tego diagramu dokonuje się prostej estymacji wymaganych zasobów w zależności od typu danego węzła i rozmiaru danych, na których węzeł przeprowadza obliczenia. Proponowana technika została zilustrowana przykładem bezstratnego kodeka FLAC. Zaprezentowane wyniki badań eksperymentalnych pokazują dokładność od 99.3% do 57%, co jest zbliżone do wyników innych zespołów badawczych, np. [2, 4]. W celu odwzorowania rdzeni do docelowego układu użyto zachłannego algorytmu Bottom-Left-Decreasing do rozwiązania dwuwymiarowego problemu pokrycia paska. Badania przeprowadzono dla różnych ograniczeń maksymalnej wysokości paska; w artykule przedstawiono wizualizacje najlepszego i najgorszego przypadku.
    Źródło:
    Pomiary Automatyka Kontrola; 2010, R. 56, nr 7, 7; 784-786
    0032-4140
    Pojawia się w:
    Pomiary Automatyka Kontrola
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-13 z 13

      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