Art

J-GLOBAL ID：201602213093814372   Reference number：16A1227037

Parameterized Algorithms for Disjoint Matchings in Weighted Graphs with Applications

アプリケーションによる加重グラフの不連続マッチングのパラメータ化アルゴリズム

Author (3)： CHEN Zhi-Zhong (Division of Information System Design, Tokyo Denki University) ,  TSUKIJI Tatsuie (Division of Information System Design, Tokyo Denki University) ,  YAMADA Hiroki (Division of Information System Design, Tokyo Denki University)
Material： IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web)  (IEICE Trans Fundam Electron Commun Comput Sci (Web))
Volume： E99.A  Issue： 6  Page： 1050-1058(J-STAGE)  Publication year： 2016 
JST Material Number： U0466A  ISSN： 1745-1337  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： theory ,  *algorithm ,  *weighting ,  matching (graph) ,  *graph ,  discontinuity ,  application program ,  graph network theory ,  graph algorithm ,  *weight
Semi thesaurus term： application program ,  *parameterized algorithms

Author keywords (5)： fixed-parameter algorithms ,  randomized algorithms ,  matchings ,  color-coding ,  universal sets

JST classification (2)： Basics of graph theory  (IA02020S) ,  Theory of computation  (JB02000A)

Reference (22)：

• [1] N. Alon, R. Yuster, and U. Zwick, “Color-coding,” J. ACM, vol.42, no.4, pp.844-856, 1995.
• [2] N.H. Bshouty, “Testers and their applications,” Electronic Colloquium on Computational Complexity, Report no.11, 2012.
• [3] J. Chen, J. Kneis, S. Lu, D. Mölle, S. Richter, P. Rossmanith, S.-H. Sze, and F. Zhang, “Randomized divide-and-conquer: Improved path, matching, and packing algorithms,” SIAM J. Comput., vol.38, no.6, pp.2526-2547, 2009.
• [4] Z.-Z. Chen, Y. Fan, and L. Wang, “Parameterized and approximation algorithms for finding two disjoint matchings,” Combinatorial Optimization and Applications, Lecture Notes in Computer Science, vol.8287, pp.1-12, Springer International Publishing, 2013.
• [5] Z.-Z. Chen, S. Konno, and Y. Matsushita, “Approximating maximum edge 2-coloring in simple graphs,” Algorithmic Aspects in Information and Management, Lecture Notes in Computer Science, vol.6124, pp.78-89, Springer Berlin Heidelberg, 2010.

Terms in the title (6)： アプリケーション ,  加重 ,  グラフ ,  不連続 ,  マッチング ,  パラメータ化アルゴリズム