Computer Science ›› 2018, Vol. 45 ›› Issue (3): 9-15.doi: 10.11896/j.issn.1002-137X.2018.03.002
Previous Articles Next Articles
KE Yu-ping and WANG Jian-xin
| [1] BODLAENDER H L,FLUITER B.On intervalizing k-coloredgraphs for DNA physical mapping[J].Discrete Applied Mathematics,1996,71(1):55-77. [2] GOLUMBIC M C,KAPLAN H,SHAMIR R.On the complexity of DNA physical mapping[J].Advances in Applied Mathema-tics,1994,15(3):251-261. [3] ROSE D J.A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations[C]∥Graph theory and Computing.1972:183-217. [4] BAR-NOY A,BAR-YEHUDA R,FREUND A,et al.A unified approach to approximating resource allocation and scheduling[J].Journal of the ACM,2001,48(5):1069-1090. [5] KRISHNAMOORTHY M S,DEO N.Node-deletion NP-com-plete problems[J].SIAM Journal on Computing,1979,8(4):619-625. [6] LEWIS J M.On the complexity of the maximum subgraph prob-lem[C]∥Proceedings of the Tenth Annual ACM Symposium on Theory of Computing.ACM,1978:265-274. [7] YANNAKAKIS M.Node-and edge-deletion NP-complete problems[C]∥Proceedings of the Tenth Annual ACM Symposium on Theory of Computing.ACM,1978:253-264. [8] LEWIS J M,YANNAKAKIS M.The node-deletion problem for hereditary properties is NP-complete[J].Journal of Computer and SystemSciences,1980,20(2):219-230. [9] YANNAKAKIS M.Computing the minimum fill-in is NP-complete[J].SIAM Journal on Algebraic Discrete Methods,1981,2(1):77-79. [10] BURZYN P,BONOMO F,DURN G.NP-completeness results for edge modificationproblems[J].Discrete Applied Mathema-tics,2006,154(13):1824-1844. [11] NATANZON A,SHAMIR R,SHARAN R.Complexity classification of some edge modificationproblems[J].Discrete Applied Mathematics,2001,113(1):109-128. [12] DOWNEY R G,FELLOWS M R.Fixed-parameter tractability and completeness[C]∥Complexity Theory:Current Research,Dagstubl Workshop(DBLP).1992:191-225. [13] DOWNEY R G,FELLOWS M R.Fixed-parameter tractability and completeness II:Oncompleteness for W [1][J].Theoretical Computer Science,1995,141(1):109-131. [14] CHEN J N,KANJ I A,JIA W J.Vertex cover:further observations and further improvements[J].Journal of Algorithms,2001,41(2):280-301. [15] TARJAN R E,TROJANOWSKI A E.Finding a maximum independent set[J].SIAM Journal on Computing,1977,6(3):537-546. [16] ABRAHAMSON K A,DOWNEY R G,FELLOWS M R.Fixed-parameter intractability II[C]∥Annual Symposium on Theore-tical Aspects of Computer Science.Springer,1993:374-385. [17] MCGEER P C,BRAYTON R K.Efficient algorithms for computing the longest viable pathin a combinational network[C]∥Proceedings of the 26th ACM/IEEE Design Automation Confe-rence.ACM,1989:561-567. [18] CHEN J N,FOMIN F V,LIU Y,et al.Improved algorithms forfeedback vertex set problems[J].Journal of Computer and System Sciences,2008,74(7):1188-1198. [19] DEHNE F,FELLOWS M,LANGSTON M,et al.An FPT algorithm for the undirected feedback vertex set problem[J].Theory of ComputingSystems,2007,41(3):479-492. [20] GUO J,GRAMM J,HFFNER F,et al.Compression basedfixed-parameter algorithms for feedback vertex set and edge bipartization[J].Journal of Computer and System Sciences,2006,72(8):1386-1396. [21] CAI L Z.Fixed-parameter tractability of graph modificationproblems for hereditary properties[J].Information Processing Letters,1996,58(4):171-176. [22] MARX D.Chordal deletion is fixed-parameter tractable[J].Algorithmica,2010,57(4):747-768. [23] CHEN J N,FOMIN F V,LIU Y,et al.Improved algorithms forfeedback vertex set problems[J].Journal of Computer and System Sciences,2008,74(7):1188-1198. [24] CAO Y X,MARX D.Interval deletion is fixed-parameter tractable[J].ACM Transactions on Algorithms (TALG),2015,11(3):21. [25] CAO Y X.Linear recognition of almost interval graphs[C]∥Proceedings of the Twenty-Seventh AnnualACM-SIAM Symposium on Discrete Algorithms.SIAM,2016:1096-1115. [26] VILLANGER Y,HEGGERNES P,CHRISTOPHE P,et al.Interval completion is fixedparameter tractable[J].SIAM Journal on Computing,2009,38(5):2007-2020. [27] BEVERN R,KOMUSIEWICZ C,HANNES M,et al.Measuring indifference:Unit interval vertex deletion[C]∥International Workshop on Graph-Theoretic Concepts in Computer Science.Springer,2010:232-243. [28] CAO Y X.Unit interval editing is fixed-parameter tractable[M]∥Automata,Languages,and Programming.Springer,2015:306-317. [29] KAPLAN H,SHAMIR R,TARJAN R E.Tractability of parameterized completion problemson chordal,strongly chordal,and proper interval graphs[J].SIAM Journal on Computing,1999,28(5):1906-1922. [30] ROSE D J,TARJAN R E,LUEKER G S.Algorithmic aspects of vertex eliminationon graphs[J].SIAM Journal on Computing,1976,5(2):266-283. [31] FULKERSON D,GROSS O.Incidence matrices and intervalgraphs[J].Pacific Journal of Mathematics,1965,15(3):835-855. [32] DIRAC G A.On rigid circuit graphs[J].Abhandlungen Aus Dem Mathematischen Seminarder Universitt Hamburg,1961,25(1/2):71-76. [33] CHAITIN G J.Register allocation & spilling via graph coloring[C]∥Sigplan Symposium on Computer Construction.ACM,1982:98-105. [34] ROBERTSON N,SEYMOUR P D.Graph minors.III.planartree-width[J].Journal of Combinatorial Theory,Series B,1984,36(1):49-64. [35] COURCELLE B.Graph rewriting:An algebraic and logic approach[M]∥Handbook of Theoretical Computer Science .1990:193-242. [36] REED B,SMITH K,VETTA A.Finding odd cycle transversals[J].Operations Research Letters,2004,32(4):299-301. [37] DOM M,GUO J,HFFNER F,et al.Fixed-parameter tract ability results for feedback set problems in tournaments[C]∥Italian Conference on Algorithms and Complexity.Springer,2006:320-331. [38] GEORGE A,LIU J W.Computer solution of large sparse positive definite[M]∥ Computer Solution of Large Sparse Positive Definite Systems.Prentice-Hall,1981:1-177. [39] PARTER S.The use of linear graphs in gauss elimination[J].SIAM Review,1961,3(2):119-130. [40] OHTSUKI T,CHEUNGLAP K,FUJISAWA T.Minimal triangulation of a graph and optimalpivoting order in a sparse matrix[J].Journal of Mathematical Analysis and Applications,1976,54(3):622-633. [41] BEERI C,FAGIN R,MAIER D,et al.On the desirability of acy-clicdatabase schemes[J].Journal of the ACM (JACM),1983,30(3):479-513. [42] LAURITZEN S L,SPIEGELHALTER D J.Local computations with probabilities on graphicalstructures and their application to expert systems[J].Journal of the Royal Statistical Society.Series B (Methodological),1988,50(2):157-224. [43] BODLAENDER H L,HEGGERNES P,VILLANGER Y.Faster parameterized algorithms forminimum fill-in[J].Algorithmica,2011,61(4):817-838. [44] FOMIN F V,VILLANGER Y.Subexponential parameterizedalgorithm for minimum fill-in[J].SIAM Journal on Computing,2013,42(6):2197-2216. [45] LEKKERKERKER C,BOLAND J.Representation of a finitegraph by a set of intervals on the realline[J].Fundamenta Mathematicae,1962,51(1):45-64. [46] OLARIU S.An optimal greedy heuristic to color interval graphs[J].Information Processing Letters,1991,37(1):21-25. [47] GILMORE P C,HOFFMAN A J.A characterization of comparability graphs and of interval graphs[J].Canadian Journal of Mathematics,2015,6(2):539-548. [48] BRANDSTDT A,SPINRAD J P,LE V B.Graph classes:Asurvey[M].Philadelphia,1999:50-134. [49] BENZER S.On the topology of the genetic fine structure[J].Proceedings of the National Academy of Sciences,1959,45(11):1607-1620. [50] HAJS G.Ubereine art von graphen[J].International Mathe-matische Nachrichten,1957,11(3):11-65. [51] BOOTH K S,LUEKER G S.Testing for the consecutive ones property,interval graphs,and graph planarity using PQ-tree algorithms[J].Journal of Computer and System Sciences,1976, 13(3):335-379. [52] HABIB M,MCCONNELL R,PAUL C,et al.Lex-BFS and partition refinement,with applications to transitive orientation,interval graph recognition and consecutiveones testing[J].Theoretical Computer Science,2000,234(1):59-84. [53] BERTSEKASD P,TSITSIKLIS J N.Neuro-dynamic progra-mming:an overview[C]∥Proceedings of the 34th IEEE Conference on Decisionand Control.1995:560-564. [54] GALLAI.Transitiv orientierbare graphen[J].Acta Mathematica Hungarica,1967,18(1/2):25-66. [55] GOLDBERG P W,GOLUMBIC M C,KAPLAN H,et al.Four strikes against physicalmapping of DNA[J].Journal of Computational Biology,1995,2(1):139-152. [56] TARJAN R E.Graph theory and Gaussian elimination[M]∥Sparse Matrix Computations.1975:3-22. [57] PENG H L,CHEN H K.On the interval completion of chordal graphs[J].Discrete Applied Mathematics,2006,154(6):1003-1010. [58] BODLAENDER H L,KLOKS T,KRATSCH D.Treewidth and pathwidth of permutationgraphs[J].SIAM Journal on Discrete Mathematics,1995,8(4):606-616. [59] SERNA M J,THILIKOSD M.Parameterized complexity forgraph layout problems[J].Bulletin of the EATCS,2005,86(41-65):272. [60] VAN ’T HOF P,VILLANGER Y.Proper interval vertex deletion[J].Algorithmica,2013,65(4):845-867. [61] GUTIN G,SZEIDER S,YEO A.Fixed-parameter complexity of minimum profileproblems[J].Algorithmica,2008,52(2):133-152. [62] HEGGERNES P,PAUL C,TELLE J A,et al.Interval completion with fewedges[C]∥Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing.ACM,2007:374-381. [63] BLIZNETS I,FOMIN F V,PILIPCZUK M,et al.Subexponential parameterizedalgorithm for interval completion[C]∥Proceedings of the Twenty-Seventh Annual ACM-SIAM Sympo-sium on Discrete Algorithms.SIAM,2016:1116-1131. [64] ROBERTS F S.“Indifference graphs”.Proof techniques in graphtheory[C]∥Proceedings Second Ann Arbor Graph Theory Conference.1969:139-146. [65] BOGART K P,WEST D B.A short proof that ‘proper= unit’[J].Discrete Mathematics,1999,201(1):21-23. [66] WEGNER G.Eigenschaften der Nerven homologisch einfacher Familien in Rn[D].Dissertation,Gttingen,1967. [67] ROSE D J,TARJANENDRE R,LUEKER G S.Algorithmic aspects of vertex eliminationon graphs[J].SIAM Journal on Computing,1976,5(2):266-283. [68] BERTOSSI A A.Finding hamiltonian circuits in proper interval graphs[J].Information Processing Letters,1983,17(2):97-101. [69] BLIZNETS I,FOMIN F V,PILIPCZUK M,et al.A subexponential parameterizedalgorithm for proper interval completion[C]∥European Symposium on Algorithms.Springer,2014:173-184. [70] BESSY S,PEREZ A.Polynomial kernels for proper intervalcompletion and relatedproblems[C]∥International Symposium on Fundamentals of Computation Theory.Springer,2011:229-239. |
| No related articles found! |
|
||
Home