×

zbMATH — the first resource for mathematics

Theory and applications of models of computation. 8th annual conference, TAMC 2011, Tokyo, Japan, May 23–25, 2011. Proceedings. (English) Zbl 1213.68052
Lecture Notes in Computer Science 6648. Berlin: Springer (ISBN 978-3-642-20876-8/pbk). xv, 564 p. (2011).

Show indexed articles as search result.

The articles of this volume will be reviewed individually. For the preceding conference see Zbl 1189.68012.
Indexed articles:
Pospelov, Alexey, Group-theoretic lower bounds for the complexity of matrix multiplication, 2-13 [Zbl 1330.68122]
Yap, Chee, A real elementary approach to the master recurrence and generalizations, 14-26 [Zbl 1330.68339]
Bell, Paul C.; Wong, Prudence W. H., Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines, 27-36 [Zbl 1330.68038]
Schmied, Richard; Viehmann, Claus, Approximating edge dominating set in dense graphs, 37-47 [Zbl 1330.68125]
Lingas, Andrzej; Di, Cui, Near approximation of maximum weight matching through efficient weight reduction, 48-57 [Zbl 1330.68348]
Ito, Takehiro; Demaine, Erik D., Approximability of the subset sum reconfiguration problem, 58-69 [Zbl 1330.68094]
Luo, Weizhong; Wang, Jianxin; Feng, Qilong; Guo, Jiong; Chen, Jianer, An improved kernel for planar connected dominating set, 70-81 [Zbl 1333.05295]
Junosza-Szaniawski, Konstanty; Kratochvíl, Jan; Liedloff, Mathieu; Rossmanith, Peter; Rzążewski, Paweł, Fast exact algorithm for \(L(2,1)\)-labeling of graphs, 82-93 [Zbl 1333.05292]
Ito, Takehiro; Kawamura, Kazuto; Zhou, Xiao, An improved sufficient condition for reconfiguration of list edge-colorings in a tree, 94-105 [Zbl 1333.05112]
Iwata, Kozue; Ishiwata, Shiro; Nakano, Shin-Ichi, A compact encoding of unordered binary trees, 106-113 [Zbl 1331.68061]
Faragó, András, Low distortion metric embedding into constant dimension, 114-123 [Zbl 1331.68250]
Chen, Xue; Hu, Guangda; Sun, Xiaoming, A better upper bound on weights of exact threshold functions, 124-132 [Zbl 1332.94117]
Kamiyama, Naoyuki, Submodular function minimization under a submodular set covering constraint, 133-141 [Zbl 1332.90225]
Shioura, Akiyoshi; Suzuki, Shunya, Optimal allocation in combinatorial auctions with quadratic utility functions, 142-153 [Zbl 1331.68116]
Suzuki, Akira; Uchizawa, Kei; Zhou, Xiao, Energy and fan-in of threshold circuits computing mod functions, 154-163 [Zbl 1332.94120]
Wang, Fengming, NEXP does not have non-uniform quasipolynomial-size ACC circuits of \(o(\log \log n)\) depth, 164-170 [Zbl 1331.68086]
Chin, Francis Y. L.; Leung, Henry C. M.; Yiu, S. M., Non-adaptive complex group testing with multiple positive sets, 172-183 [Zbl 1331.68205]
van der Zwaan, Ruben; Berger, André; Grigoriev, Alexander, How to cut a graph into many pieces, 184-194 [Zbl 1331.68117]
Davoodi, Pooya; Rao, Satti Srinivasa, Succinct dynamic cardinal trees with constant time operations for small alphabet, 195-205 [Zbl 1331.68058]
Brodal, Gerth Stølting; Greve, Mark; Pandey, Vineet; Rao, Satti Srinivasa, Integer representations towards efficient counting in the bit probe model, 206-217 [Zbl 1331.68057]
Jain, Sanjay; Stephan, Frank; Teutsch, Jason, Closed left-r.e. sets, 218-229 [Zbl 1333.03108]
Jeandel, Emmanuel; Vanier, Pascal, \(\Pi^{0}_{1}\) sets and tilings, 230-239 [Zbl 1333.03109]
Zhou, Chunlai, Intuitive probability logic, 240-251 [Zbl 1258.03025]
Fu, Jie; Heinz, Jeffrey; Tanner, Herbert G., An algebraic characterization of strictly piecewise languages, 252-263 [Zbl 1331.68146]
Manthey, Bodo, Deterministic algorithms for multi-criteria TSP, 264-275 [Zbl 1331.68294]
Klavík, Pavel; Kratochvíl, Jan; Vyskočil, Tomáš, Extending partial representations of interval graphs, 276-285 [Zbl 1331.68107]
Cicerone, Serafino, Using split composition to extend distance-hereditary graphs in a generative way (extended abstract), 286-297 [Zbl 1333.05284]
Li, Angsheng; Tang, Linqing, The complexity and approximability of minimum contamination problems, 298-307 [Zbl 1331.68093]
Althaus, Ernst; Kupilas, Joschka; Naujoks, Rouven, On the low-dimensional Steiner minimum tree problem in Hamming metric, 308-319 [Zbl 1331.68087]
Brody, Joshua; Matulef, Kevin; Wu, Chenggang, Lower bounds for testing computability by small width OBDDs, 320-331 [Zbl 1331.68088]
Freivalds, Rūsiņš; Zeugmann, Thomas, On the amount of nonconstructivity in learning recursive functions, 332-343 [Zbl 1331.68120]
Brunsch, Tobias; Röglin, Heiko, A bad instance for \(k\)-means++, 344-352 [Zbl 1331.68290]
Gavenčiak, Tomáš, Catching a fast robber on interval graphs, 353-364 [Zbl 1332.91030]
Datta, Samir; Krishnamurthy, Nagarajan, Some tractable win-lose games, 365-376 [Zbl 1332.91011]
Ding, Ning; Gu, Dawu, A note on obfuscation for cryptographic functionalities of secret-operation then public-encryption, 377-389 [Zbl 1306.94047]
Liśkiewicz, Maciej; Reischuk, Rüdiger; Wölfel, Ulrich, Grey-box steganography, 390-402 [Zbl 1260.94045]
Leung, Ming Lam; Li, Yang; Zhang, Shengyu, Tight bounds on communication complexity of symmetric XOR functions in one-way and SMP models, 403-408 [Zbl 1331.68078]
Sołtys, Karolina, The hardness of median in the synchronized bit communication model, 409-415 [Zbl 1331.68080]
Brunsch, Tobias; Röglin, Heiko, Lower bounds for the smoothed number of Pareto optimal solutions, 416-427 [Zbl 1332.90232]
Fukunaga, Takuro, Approximating minimum cost source location problems with local vertex-connectivity demands, 428-439 [Zbl 1331.68152]
Iwama, Kazuo; Miyazaki, Shuichi; Yanagisawa, Hiroki, Improved approximation bounds for the student-project allocation problem with preferences over projects, 440-451 [Zbl 1331.68091]
Okamoto, Yoshio; Otachi, Yota; Uehara, Ryuhei; Uno, Takeaki, Hardness results and an exact exponential algorithm for the spanning tree congestion problem, 452-462 [Zbl 1331.68094]
Jelínková, Eva, Switching to hedgehog-free graphs is NP-complete, 463-470 [Zbl 1331.68092]
Bílka, Ondřej; Lidický, Bernard; Tesař, Marek, Locally injective homomorphism to the simple weight graphs, 471-482 [Zbl 1331.68098]
Hellouin de Menibus, Benjamin; Uno, Takeaki, Maximal matching and path matching counting in polynomial time for graphs of bounded clique width, 483-494 [Zbl 1333.05291]
Cook, Atlas F. IV; Fan, Chenglin; Luo, Jun, Hide-and-seek: algorithms for polygon walk problems, 495-504 [Zbl 1331.68249]
Langer, Alexander; Rossmanith, Peter; Sikdar, Somnath, Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract), 505-516 [Zbl 1331.68111]
Moser, Philippe, On the polynomial depth of various sets of random strings, 517-527 [Zbl 1331.68118]
Belmonte, Rémy; Heggernes, Pinar; van ’t Hof, Pim, Edge contractions in subclasses of chordal graphs, 528-539 [Zbl 1331.68097]
Datta, Samir; Prakriya, Gautam, Planarity testing revisited, 540-551 [Zbl 1331.68102]
Meier, Arne; Schneider, Thomas, Generalized satisfiability for the description logic \(\mathcal{ALC}\) (extended abstract), 552-562 [Zbl 1331.68113]

MSC:
68-06 Proceedings, conferences, collections, etc. pertaining to computer science
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
00B25 Proceedings of conferences of miscellaneous specific interest
PDF BibTeX XML Cite
Full Text: DOI