2006-11-01から1ヶ月間の記事一覧
Dong Xin, Jiawei Han, Xifeng Yan and Hong Cheng Data & Knowledge Engineering Volume 60, Issue 1 , January 2007, Pages 5-29 http://dx.doi.org/10.1016/j.datak.2006.01.006頻出パターンの数が膨大なので，それらを代表するようなパターンを求める問…
Hua-Ming Xing, Xin Chen and Xue-Gang Chen Discrete Mathematics Volume 306, Issue 24 , 28 December 2006, Pages 3338-3340 http://dx.doi.org/10.1016/j.disc.2006.06.018一部で流行っているRoman dominationに関する研究． グラフのRoman dominationと…
Komei Fukuda and Antoine Musitelli Discrete Mathematics Volume 306, Issue 24 , 28 December 2006, Pages 3302-3306 http://dx.doi.org/10.1016/j.disc.2006.06.015お世話になりっぱなしの福田先生の論文． 行列Mに対して，その(列)基底Bを考える．非基…
Pinar Heggernes and Daniel Lokshtanov Discrete Mathematics Volume 306, Issue 24 , 28 December 2006, Pages 3267-3280 http://dx.doi.org/10.1016/j.disc.2006.06.013WG2005で聞いた話． グラフのbroadcast dominationはErwin (2004) が提案した概念で…
Roland Glantz and Marcello Pelillo Discrete Mathematics Volume 306, Issue 24 , 28 December 2006, Pages 3253-3266 http://dx.doi.org/10.1016/j.disc.2006.06.003Arratia, Bollobas, and Sorkin (SODA 2000) が提案したグラフのinterlace polynomialを…
Kazutoshi Ando Discrete Mathematics Volume 306, Issue 24 , 28 December 2006, Pages 3181-3188 http://dx.doi.org/10.1016/j.disc.2006.04.034お世話になっている安藤さんの論文．謝辞に名前を入れていただいてありがとうございます． 閉包空間に「端点…
Michael Holcomb Topology and its Applications Volume 154, Issue 1 , 1 January 2007, Pages 124-143 http://dx.doi.org/10.1016/j.topol.2006.04.003平面上のある2点を結ぶ3つのpolygonal linkage (「折れ尺」のようなもの) の配位空間のトポロジーを調…
Ole J. Mengshoel, David C. Wilkins and Dan Roth Artificial Intelligence Volume 170, Issues 16-17 , November 2006, Pages 1137-1174 http://dx.doi.org/10.1016/j.artint.2006.09.003「ランダム」なベイジアン・ネットワークに対してHuginのアルゴリズ…
Petr Kolman and Christian Scheideler Journal of Algorithms Volume 61, Issue 1 , September 2006, Pages 20-44 http://dx.doi.org/10.1016/j.jalgor.2004.07.006SODA2004論文のジャーナル版．ようやく出た． Unsplittable flow problem (多品種流問題の0…
Jiong Guo, Jens Gramm, Falk Huffner, Rolf Niedermeier and Sebastian Wernicke Journal of Computer and System Sciences Volume 72, Issue 8 , December 2006, Pages 1386-1396 http://dx.doi.org/10.1016/j.jcss.2006.02.001WADS2005の論文． 「Iterati…
http://qwiki.caltech.edu/wiki/Complexity_Zoo 専門家なら皆知っているページ．もちろんSNPもSUBEXPもFPTもW[1]も紹介されている． とても重宝する．
Jianer Chen, Xiuzhen Huang, Iyad A. Kanj and Ge Xia Journal of Computer and System Sciences Volume 72, Issue 8 , December 2006, Pages 1346-1367 http://dx.doi.org/10.1016/j.jcss.2006.04.007STOC2004論文のジャーナル版． 次のような結果を示して…
S.Y. Novak Statistics & Probability Letters Volume 77, Issue 1 , 1 January 2007, Pages 95-98 http://dx.doi.org/10.1016/j.spl.2006.05.020平均0，分散σ^2の正規分布に従う独立な確率変数X，Yに対して，2XY/\sqrt{X^2+Y^2}という確率変数も平均0，分散…
Ron Wein, Jur P. van den Berg and Dan Halperin Computational Geometry Volume 36, Issue 1 , January 2007, Pages 66-87 http://dx.doi.org/10.1016/j.comgeo.2005.11.007SoCG2005の論文だけど，これはEWCG2005の特集号． 可視性グラフ(visibility graph…
Thierry de Kok, Marc van Kreveld and Maarten Loeffler Computational Geometry Volume 36, Issue 1 , January 2007, Pages 52-65 http://dx.doi.org/10.1016/j.comgeo.2005.09.005ESA2005の論文だけど，これはEWCG2005の特集号． 高階デローネ三角形分割…
Sariel Har-Peled Computational Geometry Volume 36, Issue 1 , January 2007, Pages 39-51 http://dx.doi.org/10.1016/j.comgeo.2006.02.003いわゆる「コアセット」(coreset) の論文． 例えば，与えられた複数の点からの距離の和を最小にするような球面を…
Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grune, Rolf Klein and Gunter Rote Computational Geometry Volume 36, Issue 1, January 2007, Pages 16-38 http://dx.doi.org/10.1016/j.comgeo.2005.07.004 WADS2005の論文だけど，CGTAのこの号はEWC…
Oswin Aichholzer, and Hannes Krasser Computational Geometry Volume 36, Issue 1, January 2007, Pages 2-15 http://dx.doi.org/10.1016/j.comgeo.2005.07.005SoCG2005の論文だけど，CGTAのこの号はEWCG2005の特集号． 彼らの作っている順序タイプ (order…
Nicholas J. A. Harvey FOCS 2006 http://theory.lcs.mit.edu/~nickh/Publications/Publications.html日本好きとして一部で有名なHarveyの論文． グラフの最大マッチングを高速行列積計算を用いて求めるアルゴリズムが2004年にMucha and Sankowskiが提出した…
もちろん，Coppersmith-Winogradのアルゴリズムを使えばオーダーnの2.376乗で計算できるが，これは実用的でないと考えられている． ということで，ちょっと考えたらO(n^3 / log n)という計算量のシンプルなアルゴリズムを思いついた． 「ふむ，これはなかな…
Adam Kasperski and Pawel Zielinski European Journal of Operational Research Volume 177, Issue 2 , 1 March 2007, Pages 851-864 http://dx.doi.org/10.1016/j.ejor.2005.12.033マトロイドの最小重み基を求める問題を考えるが，要素の重みがある閉区間…
Gabor Nagy and Said Salhi European Journal of Operational Research Volume 177, Issue 2 , 1 March 2007, Pages 649-672 http://dx.doi.org/10.1016/j.ejor.2006.04.004配置問題と配送計画問題を別々にしないアプローチに関するサーベイ． EJORはサーベ…
Qun Chen, Andrew Lim, Kian Win Ong and Jiqing Tang Data & Knowledge Engineering Volume 59, Issue 3, December 2006, Pages 681-699 http://dx.doi.org/10.1016/j.datak.2005.11.002XML文書へのXPath型質問は親子関係や先祖子孫関係だけではない． その…
NHC秋学校の演習の時間のグループ割当を整数計画問題にして，NEOS Serverで解かせた． 手元のGLPKではかなり時間がかかったけど，NEOSではすぐ解けた．
Richard S. Bird, and Stefan Sadnicki Information Processing Letters Volume 101, Issue 1 , 16 January 2007, Pages 41-45 http://dx.doi.org/10.1016/j.ipl.2006.07.011N人が次々と順番にやって来るので，1列に並んだN個の席に順に座らせることを考える…
Faisal N. Abu-Khzam, and Michael A. Langston Information Processing Letters Volume 101, Issue 1, 16 January 2007, Pages 36-40 http://dx.doi.org/10.1016/j.ipl.2006.08.006ACiD2005論文のジャーナル版． Fellows and Langston (1988) の不思議な論…
Vardges Melkonian Information Processing Letters Volume 101, Issue 1, 16 January 2007, Pages 30-35 http://dx.doi.org/10.1016/j.ipl.2006.07.007動的transshipment problemといえば，Hoppe and Tardos (2000) の結果が有名で，多項式時間で解けること…
Uriel Feige and James R. Lee Information Processing Letters Volume 101, Issue 1, 16 January 2007, Pages 26-29 http://dx.doi.org/10.1016/j.ipl.2006.07.009グラフの最小linear arrangement問題に対する近似アルゴリズム。 Arora, Rao and Vazirani (…
Eric Mc Dermid, Christine Cheng, and Ichiro Suzuki Information Processing Letters Volume 101, Issue 1, 16 January 2007, Pages 13-19 http://dx.doi.org/10.1016/j.ipl.2006.07.005安定結婚問題に関する論文。 Irvingは最近「man-exchange stable mat…
R-Trees: Theory and Applications (Advanced Information and Knowledge Processing)作者: Yannis Manolopoulos,Alexandros Nanopoulos,Apostolos N. Papadopoulos,Yannis Theodoridis出版社/メーカー: Springer発売日: 2005/11/21メディア: ハードカバー …
