英語論文セミナー 2017

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

開催日: 7/31(月)

原稿締切: 開催日の一週間前

会場: 研究室の予定

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

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

• 氏名: 論文タイトル
• 河原木　渉吾 : 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]
• 槇　翔史：Design of $n$-Bit Reversible Adder with {LNN} Architecture`(fcs2016-belayet.pdf)
• 山内 大七洋：D. Avis, Generating rooted triangulations without repetitions, Algorithmica, vol.16, pp.618-632. [A96.pdf]
• 海沼　滉樹：Enumeration and Coding Methods for a Class of Permutations and Reversible Logical Gates (1B-KaranikasAtreas.pdf)
• 佐野　祐輔 : R.C. Read and R.E. Tarjan, Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning. Trees, Networks 5, 237-252, 1975.

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

by Hirayama

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

• Proceedings of ISMVL 2017から (~hirayama/Papers/4jkenshu-2017/ISMVL2017/start.pdf参照)
• Proceedings of Reed-Muller 2017から (~hirayama/Papers/4jkenshu-2017/RM2017/Reed-Muller.html参照)
• 過去の候補から(~hirayama/Papers/4jkenshu-20??/)
• 下記の候補から

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

• fcs2016-belayet.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
• Soeken2014_A_framework_for_reversible_circuit_complexity.pdf

下記は去年の~hirayama/Papers/4jkenshu-2016の候補です。

• csci2015-belayet.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 M2

• P. van Emde Boas, R.Kaas and E.Zijlstra, Design and implementation of an efficient proiority queue, Math. Syst. Theory, pp.99-127, 1977.