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

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 21
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ł:
Isomorphic components of Kronecker product of bipartite graphs
Autorzy:
Jha, Pranava
Klavžar, Sandi
Zmazek, Blaž
Powiązania:
https://bibliotekanauki.pl/articles/971945.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Kronecker product
bipartite graphs
graph isomorphism
Opis:
Weichsel (Proc. Amer. Math. Soc. 13 (1962) 47-52) proved that the Kronecker product of two connected bipartite graphs consists of two connected components. A condition on the factor graphs is presented which ensures that such components are isomorphic. It is demonstrated that several familiar and easily constructible graphs are amenable to that condition. A partial converse is proved for the above condition and it is conjectured that the converse is true in general.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 2; 301-309
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Note on cyclic decompositions of complete bipartite graphs into cubes
Autorzy:
Fronček, Dalibor
Powiązania:
https://bibliotekanauki.pl/articles/744154.pdf
Data publikacji:
1999
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hypercubes
bipartite graphs
factorization
Opis:
So far, the smallest complete bipartite graph which was known to have a cyclic decomposition into cubes $Q_d$ of a given dimension d was $K_{d2^{d-1}, d2^{d-2}}$. We improve this result and show that also $K_{d2^{d-2}, d2^{d-2}}$ allows a cyclic decomposition into $Q_d$. We also present a cyclic factorization of $K_{8,8}$ into Q₄.
Źródło:
Discussiones Mathematicae Graph Theory; 1999, 19, 2; 219-227
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
An attractive class of bipartite graphs
Autorzy:
Boliac, Rodica
Lozin, Vadim
Powiązania:
https://bibliotekanauki.pl/articles/743515.pdf
Data publikacji:
2001
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
bipartite graphs
structural characterization
polynomial algorithm
Opis:
In this paper we propose a structural characterization for a class of bipartite graphs defined by two forbidden induced subgraphs. We show that the obtained characterization leads to polynomial-time algorithms for several problems that are NP-hard in general bipartite graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2001, 21, 2; 293-301
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Extremal bipartite graphs with a unique k-factor
Autorzy:
Hoffmann, Arne
Sidorowicz, Elżbieta
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/743924.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
unique k-factor
bipartite graphs
extremal graphs
Opis:
Given integers p > k > 0, we consider the following problem of extremal graph theory: How many edges can a bipartite graph of order 2p have, if it contains a unique k-factor? We show that a labeling of the vertices in each part exists, such that at each vertex the indices of its neighbours in the factor are either all greater or all smaller than those of its neighbours in the graph without the factor. This enables us to prove that every bipartite graph with a unique k-factor and maximal size has exactly 2k vertices of degree k and 2k vertices of degree (|V(G)|)/2. As our main result we show that for k ≥ 1, p ≡ t mod k, 0 ≤ t < k, a bipartite graph G of order 2p with a unique k-factor meets 2|E(G)| ≤ p(p+k)-t(k-t). Furthermore, we present the structure of extremal graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 2; 181-192
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Optimal edge ranking of complete bipartite graphs in polynomial time
Autorzy:
Hung, Ruo-Wei
Powiązania:
https://bibliotekanauki.pl/articles/743901.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph algorithms
edge ranking
vertex ranking
edge-separator tree
complete bipartite graphs
Opis:
An edge ranking of a graph is a labeling of edges using positive integers such that all paths connecting two edges with the same label visit an intermediate edge with a higher label. An edge ranking of a graph is optimal if the number of labels used is minimum among all edge rankings. As the problem of finding optimal edge rankings for general graphs is NP-hard [12], it is interesting to concentrate on special classes of graphs and find optimal edge rankings for them efficiently. Apart from trees and complete graphs, little has been known about special classes of graphs for which the problem can be solved in polynomial time. In this paper, we present a polynomial-time algorithm to find an optimal edge ranking for a complete bipartite graph by using the dynamic programming strategy.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 149-159
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Magic and supermagic dense bipartite graphs
Autorzy:
Ivanco, Jaroslav
Powiązania:
https://bibliotekanauki.pl/articles/743476.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
magic graphs
supermagic graphs
bipartite graphs
Opis:
A graph is called magic (supermagic) if it admits a labelling of the edges by pairwise different (and consecutive) positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper we prove that any balanced bipartite graph with minimum degree greater than |V(G)|/4 ≥ 2 is magic. A similar result is presented for supermagic regular bipartite graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 3; 583-591
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Towards a characterization of bipartite switching classes by means of forbidden subgraphs
Autorzy:
Hage, Jurriaan
Harju, Tero
Powiązania:
https://bibliotekanauki.pl/articles/743415.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
switching classes
bipartite graphs
forbidden subgraphs
combinatorial search
Opis:
We investigate which switching classes do not contain a bipartite graph. Our final aim is a characterization by means of a set of critically non-bipartite graphs: they do not have a bipartite switch, but every induced proper subgraph does. In addition to the odd cycles, we list a number of exceptional cases and prove that these are indeed critically non-bipartite. Finally, we give a number of structural results towards proving the fact that we have indeed found them all. The search for critically non-bipartite graphs was done using software written in C and Scheme. We report on our experiences in coping with the combinatorial explosion.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 3; 471-483
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ł:
Independent cycles and paths in bipartite balanced graphs
Autorzy:
Orchel, Beata
Wojda, A.
Powiązania:
https://bibliotekanauki.pl/articles/743087.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
bipartite graphs
bi-placing
path
cycle
Opis:
Bipartite graphs G = (L,R;E) and H = (L',R';E') are bi-placeabe if there is a bijection f:L∪R→ L'∪R' such that f(L) = L' and f(u)f(v) ∉ E' for every edge uv ∈ E. We prove that if G and H are two bipartite balanced graphs of order |G| = |H| = 2p ≥ 4 such that the sizes of G and H satisfy ||G|| ≤ 2p-3 and ||H|| ≤ 2p-2, and the maximum degree of H is at most 2, then G and H are bi-placeable, unless G and H is one of easily recognizable couples of graphs. This result implies easily that for integers p and k₁,k₂,...,kₗ such that $k_i ≥ 2$ for i = 1,...,l and k₁ +...+ kₗ ≤ p-1 every bipartite balanced graph G of order 2p and size at least p²-2p+3 contains mutually vertex disjoint cycles $C_{2k₁},...,C_{2kₗ}$, unless $G = K_{3,3} - 3K_{1,1}$.
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 3; 535-549
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Cyclability in bipartite graphs
Autorzy:
Amar, D.
Flandrin, E.
Gancarzewicz, G.
Powiązania:
https://bibliotekanauki.pl/articles/255877.pdf
Data publikacji:
2009
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
graphs
cycles
bipartite graphs
Opis:
Let G = (X, Y; E) be a balanced 2-connected bipartite graph and S ⊂ V(G). We will say that S is cyclable in G if all vertices of S belong to a common cycle in G. We give sufficient degree conditions in a balanced bipartite graph G and a subset S ⊂ V(G) for the cyclability of the set S.
Źródło:
Opuscula Mathematica; 2009, 29, 4; 345-364
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
γ-labelings of complete bipartite graphs
Autorzy:
Bullington, Grady
Eroh, Linda
Winters, Steven
Powiązania:
https://bibliotekanauki.pl/articles/744504.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
γ-labelings
bipartite graphs
multipartite graphs
Opis:
Explicit formulae for the γ-min and γ-max labeling values of complete bipartite graphs are given, along with γ-labelings which achieve these extremes. A recursive formula for the γ-min labeling value of any complete multipartite is also presented.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 1; 45-54
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Random graph generator for bipartite networks modeling
Autorzy:
Chojnacki, Sz.
Kłopotek, M. A.
Powiązania:
https://bibliotekanauki.pl/articles/206054.pdf
Data publikacji:
2011
Wydawca:
Polska Akademia Nauk. Instytut Badań Systemowych PAN
Tematy:
complex networks
bipartite graphs
recommender systems
affiliation networks
Opis:
The purpose of this article is to introduce a new bipartite graph generation algorithm. Bipartite graphs consist of two types of nodes and edges join only nodes of different types. This data structure appears in various applications (e.g. recommender systems or text clustering). Both real-life datasets and formal tools enable us to evaluate only a limited set of properties of the algorithms that are used in such situations. Therefore, artificial datasets are needed to enhance development and testing of the algorithms. Our generator can be used to produce a wide range of synthetic datasets.
Źródło:
Control and Cybernetics; 2011, 40, 3; 697-714
0324-8569
Pojawia się w:
Control and Cybernetics
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Random graphs for performance evaluation of recommender systems
Autorzy:
Chojnacki, Sz.
Kłopotek, M. A.
Powiązania:
https://bibliotekanauki.pl/articles/206369.pdf
Data publikacji:
2011
Wydawca:
Polska Akademia Nauk. Instytut Badań Systemowych PAN
Tematy:
recommender systems
performance evaluation
random graphs
bipartite complex networks
Opis:
The purpose of this article is to introduce a new analytical framework dedicated to measuring performance of recommender systems. A standard approach is to assess the quality of a system by means of accuracy related statistics. However, the specificity of the environments in which recommender systems are deployed requires paying much attention to speed and memory requirements of the algorithms. Unfortunately, it is implausible to assess accurately the complexity of various algorithms with formal tools. This can be attributed to the fact that such analyses are usually based on an assumption of dense representation of underlying data structures. In real life, though, the algorithms operate on sparse data and are implemented with collections dedicated for them. Therefore, we propose to measure the complexity of recommender systems with artificial datasets that posses real-life properties. We utilize a recently developed bipartite graph generator to evaluate how the state-of-art recommender system behavior is determined and diversified by topological properties of the generated datasets.
Źródło:
Control and Cybernetics; 2011, 40, 2; 237-257
0324-8569
Pojawia się w:
Control and Cybernetics
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Analog Circuits Sizing Using the Fixed Point Iteration Algorithm with Transistor Compact Models
Autorzy:
Javid, F.
Iskander, R.
Durbin, F.
Louerat, M.-M.
Powiązania:
https://bibliotekanauki.pl/articles/398025.pdf
Data publikacji:
2012
Wydawca:
Politechnika Łódzka. Wydział Mikroelektroniki i Informatyki
Tematy:
IP analogowe
design reuse
graf dwudzielny
model tranzystora
migracja technologii
analog IP
analog sizing
bipartite graphs
transistor compact models
technology migration
Opis:
This paper presents an algorithm, based on the fixed point iteration, to solve for sizes and biases using transistor compact models such as BSIM3v3, BSIM4, PSP and EKV. The proposed algorithm simplifies the implementation of sizing and biasing operators. Sizing and biasing operators were originally proposed in the hierarchical sizing and biasing methodology [1]. They allow to compute transistors sizes and biases based on transistor compact models, while respecting the designer's hypotheses. Computed sizes and biases are accurate, and guarantee the correct electrical behavior as expected by the designer. Sizing and biasing operators interface with a Spice-like simulator, allowing possible use of all available compact models for circuit sizing and biasing over different technologies. A bipartite graph , that contains sizing and biasing operators, is associated to the design view of a circuit, it is the design procedure for the given circuit. To illustrate the effectiveness of the proposed fixed point algorithm, a folded cascode OTA is efficiently sized with a 130nm process, then migrated to a 65nm technology. Both sizing and migration are performed in a few milliseconds.
Źródło:
International Journal of Microelectronics and Computer Science; 2012, 3, 1; 7-14
2080-8755
2353-9607
Pojawia się w:
International Journal of Microelectronics and Computer Science
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 21

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