英語論文セミナー 2018

（注意！！：論文情報はまだ 2017年のままです） --> 2018バージョンになりました．

論文を読みます．４年生は各自，自分が読みたい論文を選んでください． 2014年度までは、授業の一貫としてやっていましたが、2015年度からは研究室での取り組みとして行います．

開催日: 7月末を予定

原稿締切: 開催日の一週間前までにA4（表裏）1枚のレジュメを完成させる（担当教員からOKをもらう）

会場: 研究室

発表時間 1人30分程度（発表12分，質疑応答18分）の予定

選んだ論文を記入してください．

• 氏名: 論文タイトル
• 須田静一朗：Generating Minimal k- Vertex Connected Spanning Subgraphs
• 佐々木良介：An Algorithm to Enumerate All Rectangular Dual Graphs
• 菊地翔太 : Compact_Based_Single_Error_Correcting_Codec
• 木村元春 : Reduced_complexity_polynomial_multiplier_architecture_for_finite_fields_GF2m
• 亘理大也 : The complexity of the min-max degree triangulation problem

自分が読みたい論文を選んでください． 論文は各教員が持っていますので、来てくれれば内容を見ることができます．

by Hirayama

以下から選んでみてください。

• Proceedings of ISMVL 2018から (~hirayama/Papers/4jkenshu-2018/ISMVL_2018_Accepted_draft/参照)
• 昨年の候補から(~hirayama/Papers/4jkenshu-2017/)
• 過去の候補から(~hirayama/Papers/4jkenshu-20??/)
• 下記の候補から

これらの論文のPDFおよび出典情報は、~hirayama/Papers/4jkenshu-2018/にあります。 .pdfが論文のPDFファイルで、.txtが論文の出典情報です。

• Choi2017_Reduced_complexity_polynomial_multiplier_architecture_for_finite_fields_GF2m.pdf
• Cui2017_High_Performance_Parallel_Decimal_Multipliers_Using_Hybrid_BCD_Codes.pdf
• Golubitsky2010_Synthesis_of_the_Optimal_4-bit_Reversible_Circuits.pdf
• Golubitsky2012_A_Study_of_Optimal_4-Bit_Reversible_Toffoli_Circuits_and_Their_Synthesis.pdf
• Kim2017_Efficient_bit-parallel_systolic_architecture_for_multiplication_and_squaring_over_GF2m.pdf
• Lee2017_Enhancing_Test_Compression_With_Dependency_Analysis_for_Multiple_Expansion_Ratios.pdf
• Lewandowski2013_Behavioral_model_of_integrated_qubit_gates_for_quantum_reversible_logic_design.pdf
• Morrison2011_Design_of_a_Reversible_ALU_Based_on_Novel_Programmable_Reversible_Logic_Gate_Structures.pdf
• Nagamani2018_A_Genetic_Algorithm-Based_Heuristic_Method_for_Test_Set_Generation_in_Reversible_Circuits.pdf
• Nagayama2017_A_Balanced_Decision_Tree_Based_Heuristic_for_Linear_Decomposition_of_Index_Generation_Functions.pdf
• Samanta2018_Compact_CA-Based_Single_Byte_Error_Correcting_Codec.pdf
• Sasao2017_A_Fast_Updatable_Implementation_of_Index_Generation_Functions_Using_Multiple_IGUs.pdf
• Schaeffer2017_Product_Transformation_and_Heuristic_EXOR-AND-OR_Logic_Synthesis_of_Incompletely_Specified_Functions.pdf
• Soeken2014_A_framework_for_reversible_circuit_complexity.pdf
• Takeuchi2017_BDD-Constrained_A_Search_A_Fast_Method_for_Solving_Constrained_Shortest-Path_Problems.pdf
• Ueno2017_Automatic_Generation_System_for_Multiple-Valued_Galois-Field_Parallel_Multipliers.pdf
• Ugurdag2017_Hardware_Division_by_Small_Integer_Constants.pdf

by Yamanaka

論文は `~yamanaka/Papers/4jkenshu-2017/' の中にあります． 見つからない場合は私に声をかけてください．山中が読みたいと思っている論文には(*)マークをつけてます．

Exact Exponential Algorithms

• R. Bellman, Dynamic Programming Treatment of the Travelling Salesman Problem, J. ACM, vol.9, pp.61-63, 1962.
• M. Held and R.M. Karp, A dynamic programming approach to sequencing problems, Journal of SIAM, vol.10, pp.196-210, 1962. [HK62.pdf]
• A.P. Golovach, P. Heggernes, D. Kratsch, Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs, Proc. of IWOCA 2015, pp.235-247, 2015. [GHK17.pdf]
• R.E. Tarjan and A.E. Trojanowski, Finding a maximum independent set, SIAM J. Comput. 6(3), 537-546, 1977.

Floorplans

• An O(n) algorithm for determining the subregion-tree representation of a rectangular dissection, SIAM Journal of Computing, vol.22, no.1, pp.79-101, Feb 1993.
• Z.C. Shen and C.C.N. Chu, Bounds on the Number of Slicing, Mosaic, and General Floorplans, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.22, no.10, Oct. 2003.

Algorithm and Computational Complexity

• G. Aloupis, E.D. Demaine, A. Guo, and G. Viglietta, Classic nintendo games are (computationally) hard, In Proceedings of The 7th International Conference on FUN with Algorithms (FUN 2014), Lecture Notes in Computer Science, vol.8496, pp.40-51, 2014.
• M.R. Garey and D.S. Johnson, Some simplified NP-complete graph problems, Theoretical Computer Science, vol.1, no.3, pp.237-267, 1976. [GJ76.pdf]
• M. Karchmer, R. Raz, and A. Wigderson, Super-logarithmic depth lower bounds via the direct sum in communication complexity, Computational Complexity vol.5, no.3-4, pp.191-204, 1995. [KRW95]
• V. Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete, Information Processing Letters, vol.37, pp.27-35, 1991.

Token-swapping, Amidakuji and Permutation

• A. Caprara, Sorting Permutations by Reversals and Eulerian Cycle Decompositions, SIAM Journal on Discrete Mathemtics, vol.12, no.1, pp.91--110, 1999.
• S. Felsner On the number of arrangements of pseudolines, Discrete & Computational Geometry, vol.18, pp.257-267, 1997. [F97.pdf]
• M.R. Jerrum, The Complexity of Finding Minimum-length Generator Sequences, Theoretical Computer Science, vol.36, pp.265-289, 1985. [J85.pdf]
• M. Jerrum, A Compact Representation for Permutation Groups, Journal of Algorithms vol.7, pp.60-78, 1986.
• J. Kawahara, T. Saitoh, and R. Yoshinaka, The time complexity of the token swapping problem and its parallel variants, Proc. of 11th Internatioal Conference and Workshops on Algorithms and Computation, Lecture Notes on Computer Science, vol.10167, pp.448-459, 2017

Enumeration and Counting

• (*) D. Avis, Generating rooted triangulations without repetitions, Algorithmica, vol.16, pp.618-632. [A96.pdf]
• L.A. Goldberg, Efficient Algorithms for Listing Unlabeled Graphs, Journal of Algorithms vol.13, pp.128-143, 1992. [hard copy only] (challenging)
• P.A. Golovach, P. Heggernes, D. Kratsch, Enumerating minimal connected dominating sets in graphs of bounded chordality, Theoretical Computer Science, vol.630, pp.63-75, 2016.
• P. Hanlon, Counting Interval Graphs, Transactions of the Mathematical Society, vol.272, no.2, pp.383-426, 1982. [H82.pdf] (challenging)
• S. Maxwell, M.R. Chance, and M. Koyuturk, Efficiently enumerating all connected induced subgraphs of a large molecular network, Proc of AlCoB 2014, LNBI, vol.8542, pp.171-182, 2014
• K. Tani, I. Shirakawa, and S. Tsukiyama, An Algorithm to Enumerate All Rectangular Dual Graphs, Electronics and Communications in Japan, Part 3, vol.3, pp.52-62, 1989. [TST89.pdf]
• (*) R.C. Read and R.E. Tarjan, Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning. Trees, Networks 5, 237-252, 1975.
• T Uno, Constant Time Enumeration by Amortization. In Proc. of Symposium on Algorithms and Data Structures (WADS 2015), Lecture Notes in Computer Science, vol 9214, pp.593-605, 2015. U15.pdf
• K. Wasa, H. Arimura, and T. Uno, Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph, Proc. of ISAAC 2014, pp 94-102, 2014.

Reconfiguration Problems

• T. Ito, E.D. Demaine, N.J.A. Harvey, C.H. Papadimitriou, M. Sideri, R. Uehara, Y. Uno, On the complexity of reconfiguration problems, Theoretical Computer Science, vol.412, pp.1054-1065, 2011. [IDHPSUU11.pdf]
• A.E. Mouawad, N. Nishimura, V. Raman, N. Simjour, and A. Suzuki, On the parameterized complexity of reconfiguration problems, Proc. of IPEC, LNCS, vol.8246, pp.281-294, 2013.

Misc.

A. Shafaei, M. Saeedi, and M. Pedram, Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures, in Proceedings of the 50th Annual Design Automation Conference (DAC '13), pp.1-6.

by M1 kainuma

/home/kono/kainuma/master/Paper内

• M. Sarkar and P. Ghosal and S.P. Mohanty, Reversible Circuit Synthesis Using ACO and SA based Quine-McCluskey method, Circuits and Systems (MWSCAS), 2013 IEEE 56th International Midwest Symposium on, August, 2013, pp.416--419. [Reversible Circuit Synthesis Using ACO and SA based Quine-McCluskey method.pdf]
• M. Li and Y. Zheng and M.S. Hsiao and C. Huang, Reversible Logic Synthesis Through Ant Colony Optimization, Design, Automation \& Test in Europe Conference & Exhibition (DATE), 2010, March, pp.307--310. [Reversible Logic Synthesis Through Ant Colony Optimization.pdf]
• G. Yang and X. Song and W.N.N. Hung and M.A. Perkowski, Fast synthesis of exact minimal reversible circuits using group theory, ASP-DAC '05 Proceedings of the 2005 Asia and South Pacific Design Automation Conference, 2005, pp.1002--1005. [Fast synthesis of exact minimal reversible circuits using group theory.pdf]

by M1 Sano

/home/kono/hasuko/Documents内

• Steffen Klamt and Axel von Kamp, Computing paths and cycles in biological interaction graphs, BMC Bioinformatics 2009 10:181[computing paths and cycles in biological interaction graphs.pdf]