On K_(1,k)-factorization of bipartite multigraphs

A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that （1） m ≤ kn, （2） n ≤ km, （3） km-n = kn-m ≡ 0 （mod （k^2- 1）） and （4） λ（km-n）（kn-m） ≡ 0 （mod k（k- 1）（k^2 - 1）（m ＋ n））.

Star-factorization of the Complete Bipartite Multigraphs

LetλK_(m,n)be a complete bipartite multigraph with two partite sets having m and n vertices,respectively.A K_(p,q)-factorization ofλK_(m,n)is a set of K_(p,q)-factors ofλK_(m,n)which partition the set of edges ofλK_(m,n).Whenλ=1,Martin,in[Complete bipartite factorizations by complete bipartite graphs,Discrete Math.,167/168(1997),461–480],gave simple necessary conditions for such a factorization to exist,and conjectured those conditions are always sufficient.In this paper,we will study the K_(p,q)-factorization ofλK_(m,n)for p=1,to show that the necessary conditions for such a factorization are always sufficient whenever related parameters are sufficiently large.

The spectrum of path factorization of bipartite multigraphs

LetλKm,nbe a bipartite multigraph with two partite sets having m and n vertices, respectively.A Pv-factorization ofλKm,nis a set of edge-disjoint Pv-factors ofλKm,nwhich partition the set of edges ofλKm,n.When v is an even number,Ushio,Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a Pv-factorization ofλKm,n.When v is an odd number,we have proposed a conjecture.Very recently,we have proved that the conjecture is true when v=4k-1.In this paper we shall show that the conjecture is true when v = 4k + 1,and then the conjecture is true.That is,we will prove that the necessary and sufficient conditions for the existence of a P4k+1-factorization ofλKm,nare（1）2km≤（2k+1）n,（2）2kn≤（2k+1）m,（3）m+n≡0（mod 4k+1）,（4）λ（4k+1）mn/[4k（m+n）]is an integer.

K_(1,p)~k-FACTORIZATION OF COMPLETE BIPARTITE GRAPHS

In this paper, it is shown that a sufficient condition for the existence of a K 1,p k factorization of K m,n , whenever p is a prime number and k is a positive integer, is (1) m≤p kn,(2) n≤p km,(3)p kn-m≡p km-n ≡0(mod( p 2k -1 )) and (4) (p kn-m)(p km-n) ≡0(mod( p k -1)p k×(p 2k -1)(m+n)) .

K_(1,k)-FACTORIZATION OF BIPARTITE GRAPHS

In this paper, a necessary condition for a bipartite graph λK m,n to be K 1,k factorizable and a sufficient condition for kK m,n to have a K 1,k factorization whenever k is a prime number are given.

P4κ-1-factorization of bipartite multigraphs

LetλKm,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A Pv-factorization of λKm,n is a set of edge-disjoint Pv-factors of λKm,n which partition the set of edges of λKm,n. When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a Pv-factorization of λKm,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true for v= 3. In this paper we will show that the conjecture is true when v= 4k- 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization of λKm,n is (1) (2κ - 1)m ≤ 2kn, (2) (2k - 1)n ≤ 2km, (3) m + n ≡0 (mod 4κ - 1), (4) λ(4κ - 1)mn/[2(2κ - 1)(m + n)] is an integer.

ORTHOGONAL (g,f)-FACTORIZAFIONS OF BIPARTITE GRAPHS

Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two positive integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). Then a (g, f)-factor of G is a spanning subgraph H of G such that g(x) ≤ dH(x) 5 f(x) for each x ∈ V(H). A (g, f)-factorization of G is a partition of E(G) into edge-disjoint (g, f)-factors. Let F = {F1, F2,…… ， Fm } and H be a factorization and a subgraph of G, respectively. If F, 1 ≤ i ≤ m， has exactly one edge in common with H, then it is said that ■ is orthogonal to H. It is proved that every bipartite (mg + m - 1, mf - m + 1 )-graph G has a (g, f)-factorization orthogonal to k vertex disjoint m-subgraphs of G if 2-k ≤ g(x) for all x ∈ V(G). Furthermore, it is showed that the results in this paper are best possible.

(g,f)-FACTORS WITH SPECIAL PROPERTIES IN BIPARTITE (mg,mf)-GRAPHS

Let G be a bipartite graph and g and f be two positive integer-valued functions defined on vertex set V(G) of G such that g(x)≤f(x).In this paper,some sufficient conditions related to the connectivity and edge-connectivity for a bipartite (mg,mf)-graph to have a (g,f)-factor with special properties are obtained and some previous results are generalized.Furthermore,the new results are proved to be the best possible.

The proof of Ushio's conjecture concerning path factorization of complete bipartite graphs

Let Km,n be a complete bipartite graph with two partite sets having m and n vertices, respectively. A Pv-factorization of Km,n is a set of edge-disjoint Pv-factors of Km,n which partition the set of edges of Km,n. When v is an even number, Wang and Ushio gave a necessary and sufficient condition for existence of Pv-factorization of Km,n. When k is an odd number, Ushio in 1993 proposed a conjecture. Very recently, we have proved that Ushio's conjecture is true when v = 4k - 1. In this paper we shall show that Ushio Conjecture is true when v = 4k + 1, and then Ushio's conjecture is true. That is, we will prove that a necessary and sufficient condition for the existence of a P4k+1-factorization of Km,n is (i) 2km ≤ (2k + 1)n,(ii) 2kn ≤ (2k + 1)m, (iii) m + n ≡ 0 (mod 4k + 1), (iv) (4k + 1)mn/[4k(m + n)] is an integer.

K_(p,q)-factorization of complete bipartite graphs

Let Km,n be a completebipartite graph with two partite sets having m and n vertices,respectively. A Kp,q-factorization of Km,n is a set ofedge-disjoint Kp,q-factors of Km,n which partition theset of edges of Km,n. When p=1 and q is a prime number,Wang, in his paper 'On K1,k-factorizations of a completebipartite graph' (Discrete Math, 1994, 126: 359-364),investigated the K1,q-factorization of Km,n and gave asufficient condition for such a factorization to exist. In the paper'K1,k-factorizations of complete bipartite graphs' (DiscreteMath, 2002, 259: 301-306), Du and Wang extended Wang's resultto the case that q is any positive integer. In this paper, we give a sufficient condition for Km,n to have aKp,q-factorization. As a special case, it is shown that theMartin's BAC conjecture is true when p:q=k:(k+1) for any positiveinteger k.

P_(4k-1)-factorization of complete bipartite graphs

Let Km,n be a complete bipartite graph with two partite sets having m and n vertices, respectively. A Pv-factorization of Km,n is a set of edge-disjoint Pv-factors of Km,n which partition the set of edges of Km,n. When v is an even number,Wang and Ushio gave a necessary and sufficient condition for the existence of Pv-factorization of Km,n. When v is an odd number, Ushio in 1993 proposed a conjecture. However, up to now we only know that Ushio Conjecture is true for v=3. In this paper wewill show that Ushio Conjecture is true when v=4k-1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization of Km,n is (1) (2k-1)m≤2kn, (2) (2k-1)n ≤2km, (3) m+n ≡0 (mod 4k-1), (4) (4k-1)mn/[2(2k-1)(m+n)] is an integer.integer.

On 2-Factors with Prescribed Properties in a Bipartite Graph

Liu and Yan gave the degree condition for a balanced bipartite graph G = （V1, V2; E） to have k vertex-disjoint quadrilaterals containing any given k independent edges e1,……, ek of G, respectively. They also conjectured that for any k independent edges e1,……, ek of G, G has a 2-factor with k cycles C1, C2, ……, Ck with respect to {e1, e2,……, ek} such that k - 1 of them are quadrilaterals. In this paper, we prove this conjecture.

CONNECTED [1, k]-FACTORS OF BALANCE BIPARTITE GRAPHS

In this paper, a sufficient condition for a balance bipartite graph to have a connected [1, k]-factor is given, which generalizes a known condition of a balance bipartite graph for the existence of a hamilton-path.

基于矩阵分解的二分网络社区挖掘算法

二分网络社区挖掘对复杂网络有重要的理论意义和应用价值。提出了一个基于矩阵分解的二分网络社区挖掘算法。该算法首先将二分网络分为两个部分,每个部分尽可能保存完整的社区信息,然后分别对两个部分进行递归的拆分,直至不能拆分为止。在拆分的过程中,应用矩阵分解,使得到的分解能与网络的相关矩阵的行空间尽可能接近,即尽可能保持原图的社区信息。实验结果表明,该算法在不需任何额外参数的情况下,不但能较准确地识别实际网络的社区个数,而且可以获得很好的划分效果。

基于图正则化非负矩阵分解的二分网络社区发现算法

现实世界存在大量二分网络,研究其社区结构有助于从新角度认识和理解异质复杂网络。非负矩阵分解模型能够克服二分结构的限制,有效地挖掘二分网络的潜在结构,但也存在着时间复杂度高、收敛慢等问题。该文提出一种基于图正则化的三重非负矩阵分解(NMTF)算法应用于二分网络社区发现,通过图正则化将用户子空间和目标子空间的内部连接关系作为约束项引入到三重非负矩阵分解模型中;同时将NMTF分解为两个最小化近似误差的子问题,并给出了乘性迭代算法以交替更新因子矩阵,从而简化矩阵分解迭代,加快收敛速度。实验和分析证明:对于计算机生成网络和真实网络,该文提出的社区划分方法均表现出较高的准确率和稳定性,能够快速准确地挖掘二分网络的社区结构。

二分图中含大圈的 2―因子(英文)

本文给出了均衡二分图有一个2-因子恰含 k 个大圈的度条件。设 G = (V1,V2;E) 是一个二分图,满足 |V1| = |V2| = n ≥ sk,其中 s ≥ 3 和 k ≥ 1 是两个整数。如果图 G 的最小度至少为 (1 ? 1/s)n + 1,那么 G 有一个2-因子恰含 k 个圈使得每个圈长至少为 2s。

半导体制造AMHS中悬挂式小车多因素调度方法

为提高半导体制造系统的整体性能,提出了一种考虑多因素的悬挂式小车(overhead hoist transporter,OHT)调度方法.从工作站、晶圆批、搬运系统三方面分析了搬运距离、晶圆批优先级、工作站特性、OHT利用率、等待时间5个关键因素.以成本最小作为调度目标,基于这5个因素构造了混合多因素调度模型,同时引用二分图匹配方法构建了调度模型的求解算法.最后进行了仿真实验设计和分析,结果表明该方法是有效、可行的.

基于外部因素的用户—产品二部分网络结构特性分析

产品的外部因素对用户的群集行为有很大的影响,然而在外部因素的影响下,从理论模型上分析用户的群集行为却往往被忽略,因此从理论模型角度分析了用户产品二部分网络结构特性。综合考虑了外部因素和内在属性,建立了用户选择产品的理论模型,并利用生成函数推导了用户和产品的度分布及投影后用户和产品的度分布。最后,举例分析并进行了数值模拟,发现模拟结果与理论分析结果非常吻合,证明了这种方法对于分析二部分网络结构特性是有效的。

二分图含圈与对集的一个构造性证明

给出了一个二分图G =(V1 ,V2 ;E)有一个支撑子图包含一个指定长度的圈和一个对集的度条件 .并且证明了若 |V1 |=|V2 |=n =2k ,则G有一个 2 因子恰有一个 8 圈和k 2个 4 圈或恰有k个 4 圈 .

融合信任关系和用户项目二部图的推荐算法

传统冷启动和数据稀疏性问题是推荐系统面临的两大难题。现有的大多数基于矩阵分解的推荐方法将用户孤立对待,忽略了用户之间的信任关系,从而导致推荐性能低效。提出一种融合信任关系和用户项目二部结构的矩阵分解推荐方法。该方法在对评分矩阵进行分解的基础上,加入用户信任关系和用户项目二部图结构信息,采用梯度下降算法训练模型参数。Epinions数据集上的对比实验表明,该方法有效提高了推荐系统的准确性和可靠性,尤其在冷启动和稀疏数据情况下,其推荐精度明显优于传统的推荐方法。