2007-04-01から1ヶ月間の記事一覧

Enumeration of subtrees of trees

Weigen Yan and Yeong-Nan Yeh Theoretical Computer Science Volume 369, Issues 1-3, 15 December 2006, Pages 256-268 http://dx.doi.org/10.1016/j.tcs.2006.09.002 与えられた木にいくつ部分木があるか,という問題. SzekelyとWang (2005) は頂点数nを…

List edge and list total colorings of planar graphs without 4-cycles

Jianfeng Hou, Guizhen Liu and Jiansheng Cai Theoretical Computer Science Volume 369, Issues 1-3, 15 December 2006, Pages 250-255 http://dx.doi.org/10.1016/j.tcs.2006.08.043 グラフの彩色に関するはなし. 「List Coloring Conjecture」としてよ…

The degree distribution of the generalized duplication model

G. Bebek, P. Berenbrink, C. Cooper, T. Friedetzky, J. Nadeau and S.C. Sahinalp Theoretical Computer Science Volume 369, Issues 1-3, 15 December 2006, Pages 239-249 http://dx.doi.org/10.1016/j.tcs.2006.08.045 生命進化の理論モデルに対する理…

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

Hans Kellerer and Vitaly A. Strusevich Theoretical Computer Science Volume 369, Issues 1-3, 15 December 2006, Pages 230-238 http://dx.doi.org/10.1016/j.tcs.2006.08.030 スケジューリングについて. 1機械で,release dateはなし.このとき,遅れ …

The complexity of membership problems for circuits over sets of integers

Stephen Travers Theoretical Computer Science Volume 369, Issues 1-3, 15 December 2006, Pages 211-229 http://dx.doi.org/10.1016/j.tcs.2006.08.017 MFCS2004の論文. 整数集合を計算する回路を考えるが,そのゲートは合併を取る操作∪,共通部分を取る…

Label updating to avoid point-shaped obstacles in fixed model

Farshad Rostamabadi and Mohammad Ghodsi Theoretical Computer Science Volume 369, Issues 1-3, 15 December 2006, Pages 197-210 http://dx.doi.org/10.1016/j.tcs.2006.08.038 地図のラベル付け問題について. 平面上のいくつかの点に一定の大きさの正…

Boundary labeling: Models and efficient algorithms for rectangular maps

Michael A. Bekos, Michael Kaufmann, Antonios Symvonis and Alexander Wolff Computational Geometry Volume 36, Issue 3, April 2007, Pages 215-236 http://dx.doi.org/10.1016/j.comgeo.2006.05.003Graph Drawing 2004の論文.地図のラベル付け問題に関…

Geometric spanners with applications in wireless networks

Christian Schindelhauer, Klaus Volbert and Martin Ziegler Computational Geometry Volume 36, Issue 3, April 2007, Pages 197-214 http://dx.doi.org/10.1016/j.comgeo.2006.02.001 ISAAC 2004の論文.盛んに研究されているspannerのはなし.点集合Pに…

Distance-preserving approximations of polygonal paths

Joachim Gudmundsson, Giri Narasimhan and Michiel Smid Computational Geometry Volume 36, Issue 3, April 2007, Pages 183-196 http://dx.doi.org/10.1016/j.comgeo.2006.05.002 地図上の道などはコンピュータ内部で折れ線として表現されているが,例え…

Meshing skin surfaces with certified topology

N.G.H. Kruithof and G. Vegter Computational Geometry Volume 36, Issue 3, April 2007, Pages 166-182 http://dx.doi.org/10.1016/j.comgeo.2006.01.003 Edelsbrunnerの定義したskin surfaceの三角形メッシュを作る論文で,skin surfaceの定義に現れるshr…

An intersection-sensitive algorithm for snap rounding

Mark de Berg, Dan Halperin and Mark Overmars Computational Geometry Volume 36, Issue 3, April 2007, Pages 159-165 http://dx.doi.org/10.1016/j.comgeo.2006.03.002 任意精度のアレンジメントを有限精度のアレンジメントに変換することをsnap roundin…

論文書き

〆切が今日だと言うことをすっかり忘れていたので,急いで書いて投稿.

実験準備

毎年同じ実験してるはずなのに,毎年いろいろと準備をし直してるので,大変といえば大変.

違和感

「違和感を感じる」という言い方に違和感が. つまり「感」が重なるところに変な印象を持つわけで,おそらく「違和感を持つ」と言った方がすっきりするのでは. 「嫌悪感を感じる」も「嫌悪感を持つ」とか「嫌悪感を催す」といった具合でしょうか.

基礎二広域25周年記念パーティー

行って来ました.懐かしい面々と顔を合わせて近況報告や昔話をしたり,とても楽しい時間を過ごしました. 記念文集は自分の担当分をもっとしっかり書けばよかったと若干後悔していますが,他の方の文章は楽しく拝読しました.また,年譜のところに私たちの卒…

誤信についてのコメント

さて,上で書いた「誤信」だけども,どうして人々はそのような間違いを犯してしまうんだろうか,と原因を探ってみる.おそらく「単体法は端点最適解を発見する」という知識から出発してしまうからだと思う.単体法が端点最適解を発見することは正しいし,任…

Algorithms

ALGORITHMS 1E作者: Sanjoy Dasgupta Algorithms,Christos H. Papadimitriou Algorithms,Umesh Vazirani Algorithms出版社/メーカー: McGraw-Hill Professional発売日: 2006/09/13メディア: ペーパーバック クリック: 3回この商品を含むブログ (1件) を見る…

線形計画法の誤信

「最適解を持つ線形計画問題には,端点最適解が存在する」は誤り. 必ずしも正しくない. Dasgupta, Papadimitriou, Vaziraniの「Algorithms」にはそんな感じで書いてあったけど,誤り.

実験初回

今回からPowerPointを使い出したけども、それによって学生の理解が進むようになったかはまだ分からない。 でも、いろいろとできる工夫はしてみたい。

演習問題

やはり演習問題を解くのは楽しい。

学生実験準備

明日から本格的に始まる.

On Quantum Versions of Record-Breaking Algorithms for SAT

E. Dantsin, V. Kreinovich, A. Wolpert SIGACT News, 36(4), pages 103-108, December 2005. Groverのアルゴリズムをそのまま使えば量子的に1.414^nぐらいの時間でSATが解ける,と. なるほど. この論文の目的はそれを他のSATアルゴリズムに適用するという…

離散数学への招待

離散数学への招待〈上〉作者: J.マトウシェク,J.ネシェトリル,Jir´i Matousek,Jaroslav Nesetril,根上生也,中本敦浩出版社/メーカー: シュプリンガー・フェアラーク東京発売日: 2002/12メディア: 単行本購入: 2人 クリック: 12回この商品を含むブログ (10件)…

学生実験説明会

自分が全体説明を担当.若干しゃべり過ぎたと思う.そのため少々疲れた.

授業スタート

いろいろなことをするために時間の使い方を大切に.

入出力

普段あまり触らないC言語を触っていたけど,どうもイライラしてしまった. 昔Javaで書いたものをCにただ直すだけなのだけど,入出力関係の部分がやけに汚い. 結局解決なかったので,明日に持ち越し. もう嫌になって明日やらないかもしれないけど.

実験委員会

今年度はまとめ役.

研究室公開

お疲れ様でした.

仙台

3日間いて、今日急いで帰って来ました。楽しかったですが、なんかどっと疲れたような。

グラフ理論

グラフ理論 (Springer‐Verlag GTMシリーズ)作者: R.ディーステル,Reinhard Diestel,根上生也,太田克弘出版社/メーカー: シュプリンガー・フェアラーク東京発売日: 2000/10メディア: 単行本購入: 1人 クリック: 45回この商品を含むブログ (10件) を見る最終章…