期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

二部图中求正交于星的(g,f)-染色的一个多项式算法 被引量：1

原文传递
导出
摘要 令G是一个具有顶点集V(G)和边集E(G)的二部图,且令g和f是定义 在V(G)上的两个非负整数值函数,使得对每个顶点x∈v(G)都有g(x)≤f(x). G的一个(g,f)-染色是一个推广的边染色,它满足在每个顶点x每一种颜色至 少出现g(x)次且至多出现f(x)次.给出了求二部图中满足某些约束条件且具有 最小颜色数的(g,f)-染色的一个多项式算法并证明了此结果是最好的可能.
作者 刘桂真 邓小铁
机构地区 山东大学数学与系统科学学院 香港城市大学计算机科学系
出处 《中国科学（A辑）》 CSCD 北大核心 2005年第3期334-344,共11页 Science in China(Series A)
基金 香港研究资助局研究基金(CityU 1056/01E)国家自然科学基金(批准号:10471078)高等学校 博士点专项基金(20040422004)资助项目
关键词 二部图 (g )一染色 (g )一因子 正交染色 函数 计算机技术 网络设计
分类号 O241 [理学—计算数学]
  • 相关文献

参考文献19

  • 1Zhou X, Fuse K, Nishizeki T. A linear algorithm for finding [g, f]-colofings of partial k-trees. Algorithmica. 2000, 27(3): 237-243.
  • 2Nakano S, Nishizeki T, Saito N. On the f-coloring of multigraphs. IEEE Thansactions on Circuis and Systems. 1988. 35(3): 345-353.
  • 3Coffman E G, Garey Jr M R, Johnson D S, et al. Scheduling file transfers. SIAM J Comput. 1985, 14(3):744-780.
  • 4Holyer I. The NP-completeness of edge-coloring. SIAM Journal on Computing, 1981, 10(3): 718-720.
  • 5Liu G, Zhu B. Some problems on factofizations with constraints in bipartite graphs. Discrete Appl Math,2003, 128(2): 421-434.
  • 6Caragiannis I, Kaklamanis C, Persiano E Edge coloring of bipartite graphs with constraints. Lecture Notesin Computer Science, 1999, 1672:376-386.
  • 7Downey R G, Fellows M R. Parameterized complexity. Berlin: Springer, 1999. 40-56.
  • 8Heinrich K, Hell P, Kirkpatrick D G, et al. A simple existence criterion for (9, f)-factors. Discrete Math,1990, 85(2): 315-317.
  • 9Hell P, Kirkpatrick D G. Algorithms for degree constrained graph factors of minimum deficiency. J Algorithms, 1993, 14(2): 115-138.
  • 10Anstee R E An algorithmic proof of Tutte's f-factor theorem. J Algorithms, 1985, 6(2): 112- 131.

同被引文献7

  • 1Even S, Itai A, Shamir A. A on the complexity of timetable and multicommodlty flow problems[ J]. SIAM Journal on Computing, 1976, 5 : 691-703.
  • 2I-Ioesel S. Optimization in telecommunication networks[ J]. Statistica Neerlandica, 2005, 59(2) : 180-205.
  • 3Caragiannis I, Ferreira A, Kaklamanis C, et al.. Approximate constrained bipartite edge coloring[ J]. Discrete Applied Mathematics, 2004, 143(1-3) : 54-61.
  • 4Bondy J A. Murty U S R. Graph theory and applications[ M]. The Macmllan Press LTD, 1976.
  • 5张克民,林国宁,张忠辅.图论及其应用习题解答[M].清华大学出版社.
  • 6Nishizeki T , Kashiwagi K. On the 1.1 edge-colorlng of mutigraphs[J]. SIAM J. Disc. Math, 1990, 3: 391-410.
  • 7Caragiannis I, Kaklamanis C, Persiano P. Edge coloring of bipartite graphs with constraints[ C]. In proc. of the 23rd International symposium on mathematical foundations of computer science (MFCS99), LNCS 1450, Springer, august, 1999. 771-779.

引证文献1

二级引证文献1

中国科学（A辑）
2005年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部