Computer Science ›› 2017, Vol. 44 ›› Issue (1): 1-6.doi: 10.11896/j.issn.1002-137X.2017.01.001
LUO Wei-dong, WANG Jian-xin and FENG Qi-long
| [1] ERDS P,PSA L.On the maximal number of disjoint circuits of a graph[J].Publicationes Mathematicae Debrecen,1962(9):3-12. [2] ERDS P,PSA L.On independent circuits contained in a g-raph[J].Canadia Journal of Mathematics,1965,17:347-352. [3] CARPARA A,PANCONESI A,RIZZI R.Packing cycles in undirected graphs[J].Journal of Algorithms,2003,48(1):239-256. [4] CARPARA A,PANCONESI A,RIZZI R.Packing cuts in undirected graphs[J].Networks,2004,44(1):1-11. [5] FRANK A.Conservative weightings and ear decompositions of graphs[J].Combinatorica,1993,13(1):65-81. [6] HOLYER I.The NP-completeness of some edge-partition problems[J].SIAM Journal on Computing,1981,10:713-717. [7] KRIVELEVICH M,NUTOV Z,YUSTER R.Approximationalgorithms for cycle packing problems[C]∥ Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms.Vancouver,British Columbia,Canada,2005:556-561. [8] FRIGGSTAD Z,SALAVATIPOUR M R.Approximability ofPacking Disjoint Cycles[J].Algorithmica,2010,60(2):395-400. [9] DU Ding-zhu,GE Ke-yi,HU Xiao-dong.Design and analysis of approximation algorithms[M].Beijing:China Higher Education Press,2011.(in Chinese) 堵丁柱,葛可一,胡晓东.近似算法的设计与分析[M].北京:高等教育出版社,2011. [10] GAREY M R,JOHONSON D S.Computers and Intractability:A Guide to the Theory of Incompleteness[M].San Francisco,1979. [11] CAPRARA A,RIZZI R.Packing triangles in bounded degree graphs[J].Information Processing Letters,2002,84(4):175-180. [12] RAUTENBACH D,REGEN F.On packing shortest cycles in graphs[J].Information Processing Letters,2009,109:816-821. [13] SLIVKINS A.Parameterized tractability of edge disjoint paths on directed acyclic graphs[J].SIAM Journal on Discrete Mathematics,2010,4(1):146-157. [14] GROHE M,GRUBER M.Parameterized Approximability of the Disjoint Cycle Problem[C]∥Automata,Languages and Programming,34th International Colloquium.Wroclaw,Poland,2007:363-374. [15] BODLAENDER H L,JANSEN B M P,K RATSCH S.Kernel bounds for path and cycle problems[J].Theoretical Computer Science,2013,511:117-136. [16] BODLAENDER H L,PENNINKX E,TAN R B.A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs[C]∥ Algorithms and Computation,19th International Symposium.Gold Coast,Australia,2008:306-317. [17] VOSS H J,JRGEN H,GRAPHEN E V.die keine k+1 knotenfremde Kreise enthalten[J].Mathematische Nachrichten,1969,40:19-25. [18] YOUNGER D H.Graphs with interlinked directed circuits[C]∥Proceedings of the International Midwest Symposium on Circuit and Systems.1973:XVI 2.1-XVI 2.7. [19] MCCUAIG W.Intercyclic digraphs.Graph Structure Theory[M]∥AMS Contemporary Math,1991:203-245. [20] SEYMOUR P D.Packing Directed Circuits Fractionally[J].Combinatorica,1995,15(2):281-288. [21] REED B,ROBERTSON N,Seymour P,et al.Packing Directed Circuits[J].Combinatorica,1996,16(4):535-554. [22] ENOMOTO H.On the existence of disjoint cycles in a graph[J].Combinatorica,1998,18(4):487-492. [23] WANG Hong.On the maximum number of independent cycles in a graph[J].Discrete Mathematics,1999,205(1-3):183-190. [24] 王建新,冯启龙.参数计算导论[M].长沙:科学出版社,2014. [25] EGAWA Y,HAGITA M, KAWARABAYASHI K,et al.Cove-ring vertices of a graph by k disjoint cycles[J].Discrete Mathematics,2003,270(1-3):114-124. [26] EGAWA Y,FUJITA S,KAWARABAYASHI K,et al.Exis-tence of two disjoint long cycles in graphs[J].Discrete Mathematics,2005,305(1-3):154-169. [27] BRANDT S,CHEN G,FAUDREE R,et al.Degree conditions for 2-factors[J].Journal of Graph Theory,1997,24(2):165-173. [28] ENOMOTO H,LI H.Partition of a graph into cycles and degene-rated cycles[J].Discrete Mathematics,2004,276(1-3):177-181. [29] KAWARABAYASHI K.Degree sum conditions and graphswhich are not covered by k cycles[J].Discrete Mathematics,2008,308:1620-1627. [30] HU Zhi-quan,LI Hao.Weak cycle partition involving degreesum conditions[J].Discrete Mathematics,2009,309(4):647-654. [31] FUJITA S.Degree conditions for the partition of a graph intocycles,edges and isolated vertices[J].Discrete Mathematics,2009,309(11):3534-3540. [32] FUJITA S.Recent Results on Disjoint Cycles in Graphs[J].Electronic Notes in Discrete Mathematics,2005,2:409-412. [33] PONTECORVI M,WOLLAN P.Disjoint cycles intersecting aset of vertices[J].Jounal of Combinatrias Theory,Series B,2012,102(5):1134-1141. [34] KAWARABAYASHI K,KRL D,KRCl M,et al.Packing directed cycles through a specified vertex set[C]∥ Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms.New Orleans,Louisiana,USA,2013:365-377. [35] REED B,SHEPHERD B.The Gallai-Younger conjecture forplanar graphs[J].Combinatorica,1996,16:555-566. [36] KAKIMURA N,KAWARABAYASHI K,MARX D.Packingcycles through prescribed vertices[J].Journal of Combinational Theory,2011,1(5):378-381. [37] KAKIMURA N,KAWARABAYASHI K.Packing Directed Circuits through Prescribed Vertices Bounded Fractionally[J].SIAM Jounal of Discrete Mathematics,2012,6(3):1121-1133. [38] CORRDI K,HAJNAL A.On the maximal number of inde-pendent circuits in a graph[J].Acta Mathematics,1963,14:423-443. [39] CHIBA S,FUJITA S,KAWARABAYASHI K,et al.DisjointEven Cycles Packing[J].Electronic Notes in Discrete Mathematics,2009,34:113-119. [40] JUSTESEN P.On independent circuits in nite graphs and a conjecture of Erds and Pósa[J].Annals of Discrete Mathematics,1989,41:299-306. [41] WANG Hong.Independent cycles with limited size in a graph[J].Graphs and Combinatorial,1994,10:271-281. [42] GEELEN J,GERARDS B,REED B,et al.On the odd-minor variant of Hadwiger’s conjecture[J].Journal of Combinatorial Theory,Series B,2009,99:20-29. [43] METZLAR A,MURTY U S R.Disjoint Circuits in Planar Digraphs[J].Journal of Combinatorial,Theory Series B,1993,57(2):228-238. [44] KANN V.Maximum bounded 3-dimensional matching is MAX SNP-complete[J].Information Processing Letters,1991,37:27-35. [45] AUSIELLO G,CRESCENZI P,Gambosi G,et al.Combinatorial Optimization Problems and Their Approximability Properties[M].Berlin:Springer,1999. [46] HURKENS C A J,SCHRIJVER A.On the size of systems of sets every t,of which have an SDR,with an application to the worstcase ratio of heuristics for packing problems[J].SIAM Journal on Discrete Mathematics,1989,2(1):68-72. [47] EIMABROUK N.Genome Rearrangement by Reversals and Insertions/Deletions of Contiguous Segments[C]∥ Combinatorial Pattern Matching,11th Annual Symposium.Montreal,Canada,2000:222-234. [48] BAFNA V,PEVZNER P A.Genome Rearrangements and Sorting by Reversals[J].SIAM Journal on Computing,1996,25(2):272-289. [49] SHAO Ming-fu,LIN Yu.Approximating the edit distance for genomes with duplicate genes under DCJ,insertion and deletion[J].BMC Bioinformatics,2012,13(S-19):S13. [50] SHAO Ming-fu,LIN Yu,BERNARD M.An Exact Algorithm to Compute the DCJ Distance for Genomes with Duplicate Genes[C]∥ Research in Computational Molecular Biology 19th Annual International Conference.Pittsburgh,PA,USA,2014:280-292. [51] CHEN Xin,ZHENG Jie,FU Zheng,et al.Assignment of ortho-logous genes via genome rearrangement[J].IEEE/ACM Tran-sactions on Computational Biology Bioinformatics,2005,2(4):302-315. [52] LI Shao-hua,WANG Jian-xin,FENG Qi-long,et al.Kerneliza-tion techniques and its application to parameterized computation[J].Journal of Software,2009,0(9):2307-2319.(in Chinese) 李绍华,王建新,冯启龙,等.参数计算中核心化计算及其应用的研究进展[J].软件学报,2009,0(9):2307-2319. [53] ZHOU Xing,PENG Wei.Several techniques used in paramete-rized computation[J].Computer Science,2014,41(6A):18-23.(in Chinese) 周星,彭伟.参数计算中使用的若干技术[J].计算机科学,2014,41(6A):18-23. [54] LU Sheng-guo,LI Shuang,ZHU Jian-guo,et al.Survey of genome rearrangements[J].China Biotechnology,2013,30(7):108-111.(in Chinese) 卢胜国,李霜,朱建国,等.基因组重排技术应用及进展[J].中国生物工程杂志,2013,30(7):108-111. |
| No related articles found! |
|
||
Home