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ł:
A Characterization for 2-Self-Centered Graphs
Autorzy:
Shekarriz, Mohammad Hadi
Mirzavaziri, Madjid
Mirzavaziri, Kamyar
Powiązania:
https://bibliotekanauki.pl/articles/31342444.pdf
Data publikacji:
2018-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
self-centered graphs
specialized bi-independent covering (SBIC)
generalized complete bipartite graphs (GCB)
Opis:
A graph is called 2-self-centered if its diameter and radius both equal to 2. In this paper, we begin characterizing these graphs by characterizing edge-maximal 2-self-centered graphs via their complements. Then we split characterizing edge-minimal 2-self-centered graphs into two cases. First, we characterize edge-minimal 2-self-centered graphs without triangles by introducing specialized bi-independent covering (SBIC) and a structure named generalized complete bipartite graph (GCBG). Then, we complete characterization by characterizing edge-minimal 2-self-centered graphs with some triangles. Hence, the main characterization is done since a graph is 2-self-centered if and only if it is a spanning subgraph of some edge-maximal 2-self-centered graphs and, at the same time, it is a spanning supergraph of some edge-minimal 2-self-centered graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 1; 27-37
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
One-Three Join: A Graph Operation and Its Consequences
Autorzy:
Shalu, M.A.
Devi Yamini, S.
Powiązania:
https://bibliotekanauki.pl/articles/31341697.pdf
Data publikacji:
2017-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
one-three join
bipartite-join
homogeneous set
odd hole-free graphs
Opis:
In this paper, we introduce a graph operation, namely one-three join. We show that the graph G admits a one-three join if and only if either G is one of the basic graphs (bipartite, complement of bipartite, split graph) or G admits a constrained homogeneous set or a bipartite-join or a join. Next, we define ℳH as the class of all graphs generated from the induced subgraphs of an odd hole-free graph H that contains an odd anti-hole as an induced subgraph by using one-three join and co-join recursively and show that the maximum independent set problem, the maximum clique problem, the minimum coloring problem, and the minimum clique cover problem can be solved efficiently for ℳH.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 3; 633-647
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
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ł:
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ł:
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ł
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ł:
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ł:
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ł:
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ł:
A note on bipartite graphs whose [1, k]-domination number equal to their number of vertices
Autorzy:
Ghareghani, Narges
Peterin, Iztok
Sharifani, Pouyeh
Powiązania:
https://bibliotekanauki.pl/articles/256007.pdf
Data publikacji:
2020
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
domination
[1, k]-domination number
[l,k]-total domination number
bipartite graphs
Opis:
A subset D of the vertex set V of a graph G is called an [1, k]-dominating set if every vertex from V — D is adjacent to at least one vertex and at most fc vertices of D. A [1, k]-dominating set with the minimum number of vertices is called a [formula]-set and the number of its vertices is the [1, k]-domination number [formula] of G. In this short note we show that the decision problem whether [formula] is an NP-hard problem, even for bipartite graphs. Also, a simple construction of a bipartite graph G of order n satisfying [formula] is given for every integer n ≥ (k + l)(2k + 3).
Źródło:
Opuscula Mathematica; 2020, 40, 3; 375-382
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
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ł:
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ł:
Vertex-Distinguishing IE-Total Colorings of Complete Bipartite Graphs Km,N(m < n)
Autorzy:
Chen, Xiang’en
Gao, Yuping
Yao, Bing
Powiązania:
https://bibliotekanauki.pl/articles/30146641.pdf
Data publikacji:
2013-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
complete bipartite graphs
IE-total coloring
vertex-distinguishing IE-total coloring
vertex-distinguishing IE-total chromatic number
Opis:
Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. Let C(u) be the set of colors of vertex u and edges incident to u under f. For an IE-total coloring f of G using k colors, if C(u) ≠ C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G, or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt(G), and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. VDIET colorings of complete bipartite graphs Km,n(m < n) are discussed in this paper. Particularly, the VDIET chromatic numbers of Km,n(1 ≤ m ≤ 7, m < n) as well as complete graphs Kn are obtained.
Źródło:
Discussiones Mathematicae Graph Theory; 2013, 33, 2; 289-306
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
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