Computing and combinatorics. 11th annual international conference, COCOON 2005, Kunming, China, August 16--29, 2005. Proceedings. (Q2577425)

The articles of this volume will be reviewed individually. The preceding conference has been reviewed (see Zbl 1053.68004). Indexed articles: \textit{Valiant, Leslie G.}, Completeness for parity problems, 1-8 [Zbl 1128.68359] \textit{Wu, Shiquan; Gu, Xun}, Gene network: Model, dynamics and simulation, 12-21 [Zbl 1128.92322] \textit{Blin, Guillaume; Rizzi, Romeo}, Conserved interval distance computation between non-trivial genomes, 22-31 [Zbl 1128.92316] \textit{Bereg, Sergey; Zhu, Binhai}, RNA multiple structural alignment with longest common subsequences, 32-41 [Zbl 1124.68453] \textit{Sagot, Marie-France; Tannier, Eric}, Perfect sorting by reversals, 42-51 [Zbl 1128.68350] \textit{Zheng, Chunfang; Sankoff, David}, Genome rearrangements with partially ordered chromosomes, 52-62 [Zbl 1128.92323] \textit{Liu, Tao; Tang, Jijun; Moret, Bernard M. E.}, Quartet-based phylogeny reconstruction from gene orders, 63-73 [Zbl 1128.92324] \textit{Tan, Jinsong; Chua, Kok Seng; Zhang, Louxin}, Algorithmic and complexity issues of three clustering methods in microarray data analysis, 74-83 [Zbl 1124.68377] \textit{Nakhleh, Luay; Ruths, Derek; Wang, Li-San}, RIATA-HGT: A fast and accurate heuristic for reconstructing horizontal gene transfer, 84-93 [Zbl 1128.92321] \textit{Li, Hengwu; Zhu, Daming}, A new pseudoknots folding algorithm for RNA structure prediction, 94-103 [Zbl 1128.92303] \textit{Csűrös, Miklós; Ma, Bin}, Rapid homology search with two-stage extension and daughter seeds, 104-114 [Zbl 1128.92300] \textit{Berry, Vincent; Guillemot, Sylvain; Nicolas, François; Paul, Christophe}, On the approximation of computing evolutionary trees, 115-125 [Zbl 1128.68554] \textit{Li, Xiang-Yang; Wan, Peng-Jun}, Theoretically good distributed CDMA/OVSF code assignment for wireless ad hoc networks, 126-135 [Zbl 1128.68306] \textit{Cai, Zhipeng; Lin, Guohui; Xue, Guoliang}, Improved approximation algorithms for the capacitated multicast routing problem, 136-145 [Zbl 1128.68555] \textit{Zeng, Jianyang; Hsu, Wen-Jing; Zhou, Suiping}, Construction of scale-free networks with partial information, 146-155 [Zbl 1128.68311] \textit{Desmedt, Yvo; Wang, Yongge; Safavi-Naini, Rei; Wang, Huaxiong}, Radio networks with reliable communication, 156-166 [Zbl 1128.68300] \textit{Hoefer, Martin; Krysta, Piotr}, Geometric network design with selfish agents, 167-178 [Zbl 1128.68302] \textit{Krysta, Piotr}, Bicriteria network design via iterative rounding, 179-187 [Zbl 1128.68305] \textit{Kuhn, Fabian; von Rickenbach, Pascal; Wattenhofer, Roger; Welzl, Emo; Zollinger, Aaron}, Interference in cellular networks: The minimum membership set cover problem, 188-198 [Zbl 1128.90319] \textit{Chen, Xujin; Hu, Xiaodong; Shuai, Tianping}, Routing and coloring for maximal number of trees, 199-209 [Zbl 1128.68399] \textit{Wang, WeiZhao; Li, Xiang-Yang; Sun, Zheng}, Share the multicast payment fairly, 210-219 [Zbl 1128.68310] \textit{Li, Jianping; Li, Kang; Law, Ken C. K.; Zhao, Hao}, On packing and coloring hyperedges in a cycle, 220-229 [Zbl 1128.90576] \textit{Liu, Hai; Wan, Peng-Jun; Jia, Xiaohua}, Fault-tolerant relay node placement in wireless sensor networks, 230-239 [Zbl 1128.68325] \textit{Ono, Hirotaka; Ng, Yen Kaow}, Best fitting fixed-length substring patterns for a set of strings, 240-250 [Zbl 1128.68365] \textit{Caminiti, Saverio; Petreschi, Rossella}, String coding of trees with locality and heritability, 251-262 [Zbl 1128.68397] \textit{Liben-Nowell, David; Vee, Erik; Zhu, An}, Finding longest increasing and common subsequences in streaming data, 263-272 [Zbl 1128.68543] \textit{Na, Joong Chae; Giancarlo, Raffaele; Park, Kunsoo}, \(O ( n^{2} \log n )\) time on-line construction of two-dimensional suffix trees, 273-282 [Zbl 1128.68347] \textit{Li, Minming; Liu, Becky Jie; Yao, Frances F.}, Min-energy voltage allocation for tree-structured tasks, 283-296 [Zbl 1128.68337] \textit{Tan, Zhiyi; He, Yong}, Semi-online problems on identical machines with inexact partial information, 297-307 [Zbl 1128.68342] \textit{Baille, Fabien; Bampis, Evripidis; Laforest, Christian; Thibault, Nicolas}, On-line simultaneous maximization of the size and the weight for degradable intervals schedules, 308-317 [Zbl 1128.68326] \textit{Chan, Wun-Tat; Chin, Francis Y. L.; Zhang, Yong; Zhu, Hong; Shen, Hong; Wong, Prudence W. H.}, Off-line algorithms for minimizing total flow time in broadcast scheduling, 318-328 [Zbl 1128.68329] \textit{Chung, Fan; Graham, Ron; Mao, Jia; Yao, Andrew}, Oblivious and adaptive strategies for the majority and plurality problems, 329-338 [Zbl 1124.68395] \textit{Cai, Jin-Yi; Chakaravarthy, Venkatesan T.}, A note on zero error algorithms having oracle access to one NP query, 339-348 [Zbl 1128.68358] \textit{Ko, Ker-I; Yu, Fuxiang}, On the complexity of computing the logarithm and square root functions on a complex domain, 349-358 [Zbl 1128.68364] \textit{Rettinger, Robert; Zheng, Xizhong}, Solovay reducibility on d-c.e. real numbers, 359-368 [Zbl 1128.03307] \textit{Martinez, Fábio Viduani; Coelho de Pina, José; Soares, José}, Algorithms for terminal Steiner trees, 369-379 [Zbl 1128.68557] \textit{Chalermsook, Parinya; Fakcharoenphol, Jittat}, Simple distributed algorithms for approximating minimum Steiner trees, 380-389 [Zbl 1128.68550] \textit{Gualà, Luciano; Proietti, Guido}, A truthful \((2 -2/k\))-approximation mechanism for the Steiner tree problem with \(k\) terminals, 390-400 [Zbl 1128.68556] \textit{Bachmaier, Christian; Fischer, Florian; Forster, Michael}, Radial coordinate assignment for level graphs, 401-410 [Zbl 1128.68395] \textit{Yang, Guowu; Song, Xiaoyu; Yang, Hannah H.; Xie, Fei}, A theoretical upper bound for IP-based floorplanning, 411-419 [Zbl 1128.68394] \textit{Hallgren, Sean; Russell, Alexander; Shparlinski, Igor E.}, Quantum noisy rational function reconstruction, 420-429 [Zbl 1128.68559] \textit{Zhang, Shengyu}, Promised and distributed quantum search, 430-439 [Zbl 1128.68352] \textit{Viger, Fabien; Latapy, Matthieu}, Efficient and simple generation of random simple connected graphs with prescribed degree sequence, 440-449 [Zbl 1128.05312] \textit{List, Beatrice; Maucher, Markus; Schöning, Uwe; Schuler, Rainer}, Randomized Quicksort and the entropy of the random source, 450-460 [Zbl 1128.68349] \textit{Sankowski, Piotr}, Subquadratic algorithm for dynamic shortest distances. Extended abstract, 461-470 [Zbl 1128.68553] \textit{Ding, Q.; Qian, J.; Tsang, W.; Wang, C.}, Randomly generating triangulations of a simple polygon, 471-480 [Zbl 1128.68518] \textit{Xu, Yinfeng; Dai, Wenqiang; Katoh, Naoki; Ohsaki, Makoto}, Triangulating a convex polygon with small number of non-standard bars. Extended abstract, 481-489 [Zbl 1128.68524] \textit{Chen, Zhixiang; Fu, Bin; Tang, Yong; Zhu, Binhai}, A PTAS for a disc covering problem using width-bounded separators, 490-503 [Zbl 1128.68517] \textit{Wu, Xiaodong}, Efficient algorithms for intensity map splitting problems in radiation therapy, 504-513 [Zbl 1128.92312] \textit{Lefmann, Hanno}, Distributions of points in \(d\) dimensions and large \(k\)-point simplices. Extended abstract, 514-523 [Zbl 1128.68519] \textit{Icking, Christian; Kamphans, Tom; Klein, Rolf; Langetepe, Elmar}, Exploring simple grid polygons, 524-533 [Zbl 1128.68504] \textit{Tan, Xuehou}, Approximation algorithms for cutting out polygons with lines and rays, 534-543 [Zbl 1128.68523] \textit{Gupta, Prosenjit; Janardan, Ravi; Smid, Michiel}, Efficient non-intersection queries on aggregated geometric data, 544-553 [Zbl 1128.68346] \textit{Ackerman, Eyal; Barequet, Gill; Pinter, Ron Y.}, An upper bound on the number of rectangulations of a point set, 554-559 [Zbl 1128.68516] \textit{Poon, Chung Keung; Yiu, Wai Keung}, Opportunistic data structures for range queries, 560-569 [Zbl 1128.68348] \textit{Ruskey, Frank; Williams, Aaron}, Generating combinations by prefix shifts, 570-576 [Zbl 1128.68393] \textit{Braeken, An; Nikov, Ventzislav; Nikova, Svetla}, Error-set codes and related objects, 577-585 [Zbl 1128.94307] \textit{Deng, Xiaotie; Huang, Li-Sha; Li, Minming}, On Walrasian price of CPU time. Extended abstract, 586-595 [Zbl 1128.91331] \textit{Angelopoulos, Spyros; Sarma, Atish Das; Magen, Avner; Viglas, Anastasios}, On-line algorithms for market equilibria, 596-607 [Zbl 1128.91318] \textit{Kothari, Anshul; Suri, Subhash; Zhou, Yunhong}, Interval subset sum and uniform-price auction clearing, 608-620 [Zbl 1128.91321] \textit{Bae, Sung E.; Takaoka, Tadao}, Improved algorithms for the \(k\)-maximum subarray problem for small \(k\), 621-631 [Zbl 1128.68563] \textit{Chaudhuri, Kamalika; Kothari, Anshul; Pendavingh, Rudi; Swaminathan, Ram; Tarjan, Robert; Zhou, Yunhong}, Server allocation algorithms for tiered systems, 632-643 [Zbl 1128.68539] \textit{Xu, Guang; Xu, Jinhui}, An improved approximation algorithm for uncapacitated facility location problem with penalties, 644-653 [Zbl 1128.90554] \textit{Chrobak, Marek; Kenyon, Claire; Young, Neal E.}, The reverse greedy algorithm for the metric \(K\)-median problem, 654-660 [Zbl 1128.90549] \textit{Ma, Guoxuan; Peng, Jiming; Wei, Yu}, On approximate balanced bi-clustering, 661-670 [Zbl 1128.90564] \textit{Wang, Tao-Ming}, Toroidal grids are anti-magic, 671-679 [Zbl 1128.05311] \textit{Chen, Xiaomin; Szegedy, Mario; Wang, Lei}, Optimally balanced forward degree sequence, 680-689 [Zbl 1128.05302] \textit{Dubey, Chandan K.; Mehta, Shashank K.; Deogun, Jitender S.}, Conditionally critical indecomposable graphs, 690-700 [Zbl 1128.05307] \textit{Cardinal, Jean; Labbé, Martine; Langerman, Stefan; Levy, Eythan; Mélot, Hadrien}, A tight analysis of the maximal matching heuristic, 701-709 [Zbl 1128.68398] \textit{Jowhari, Hossein; Ghodsi, Mohammad}, New streaming algorithms for counting triangles in graphs, 710-716 [Zbl 1128.05317] \textit{Suters, W. Henry; Abu-Khzam, Faisal N.; Zhang, Yun; Symons, Christopher T.; Samatova, Nagiza F.; Langston, Michael A.}, A new approach and faster exact methods for the maximum common subgraph problem, 717-727 [Zbl 1128.05308] \textit{Allulli, Luca; Ausiello, Giorgio; Laura, Luigi}, On the power of lookahead in on-line vehicle routing problems, 728-736 [Zbl 1128.90574] \textit{Misiołek, Ewa; Chen, Danny Z.}, Efficient algorithms for simplifying flow networks, 737-746 [Zbl 1128.90578] \textit{Fukunaga, Takuro; Nagamochi, Hiroshi}, Approximation algorithms for the \(b\)-edge dominating set problem and its related problems, 747-756 [Zbl 1128.90575] \textit{Dom, Michael; Guo, Jiong; Niedermeier, Rolf}, Bounded degree closest \(k\)-tree power is NP-complete, 757-766 [Zbl 1128.68363] \textit{Khachiyan, Leonid; Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir}, A new algorithm for the hypergraph transversal problem, 767-776 [Zbl 1128.05306] \textit{Gómez, Domingo; Gutierrez, Jaime; Ibeas, Álvar; Martínez, Carmen; Beivide, Ramón}, On finding a shortest path in circulant graphs with two jumps, 777-786 [Zbl 1128.05305] \textit{Hsu, Wen-Lian}, A linear time algorithm for finding a maximal planar subgraph based on PC-trees, 787-797 [Zbl 1128.05315] \textit{Ito, Takehiro; Kato, Akira; Zhou, Xiao; Nishizeki, Takao}, Algorithms for finding distance-edge-Colorings of graphs, 798-807 [Zbl 1128.05316] \textit{Chang, Maw-Shang; Kloks, Ton; Kratsch, Dieter; Liu, Jiping; Peng, Sheng-Lung}, On the recognition of probe graphs of some self-complementary classes of perfect graphs, 808-817 [Zbl 1128.05313] \textit{Liao, Chung-Shou; Lee, Der-Tsai}, Power domination problem in graphs, 818-828 [Zbl 1128.90577] \textit{Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel}, Complexity and approximation of satisfactory partition problems, 829-838 [Zbl 1128.68396] \textit{Grandoni, Fabrizio; Könemann, Jochen; Panconesi, Alessandro}, Distributed weighted vertex cover via maximal matchings, 839-848 [Zbl 1128.68401] \textit{Kára, Jan; Kratochvíl, Jan; Wood, David R.}, On the complexity of the balanced vertex ordering problem, 849-858 [Zbl 1128.68402] \textit{Dehne, Frank; Fellows, Michael; Langston, Michael A.; Rosamond, Frances; Stevens, Kim}, An \(O (2^{ O (k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem, 859-869 [Zbl 1128.68400] \textit{Chen, Guantao; Gao, Zhicheng; Yu, Xingxing; Zang, Wenan}, Approximating the longest cycle problem on graphs with bounded degree, 870-884 [Zbl 1128.05303] \textit{He, Yong; Dósa, György}, Bin packing and covering problems with rejection, 885-894 [Zbl 1128.90568] \textit{Hemaspaandra, Lane A.; Thakur, Mayur}, Query-monotonic Turing reductions, 895-904 [Zbl 1123.68333] \textit{Ibarra, Oscar H.; Woodworth, Sara; Yen, Hsu-Chun; Dang, Zhe}, On sequential and 1-deterministic P systems, 905-914 [Zbl 1128.68357] \textit{Huang, Xiaofei}, Global optimality conditions and near-perfect optimization in coding, 915-924 [Zbl 1128.90565] \textit{Kutz, Martin; Pór, Attila}, Angel, devil, and king, 925-934 [Zbl 1128.91312] \textit{Cicalese, Ferdinando; Damaschke, Peter; Tansini, Libertad; Werth, Sören}, Overlaps help: Improved bounds for group testing with interval queries, 935-944 [Zbl 1116.68673] \textit{Yoon, Eun-Jun; Yoo, Kee-Young}, New efficient simple authenticated key agreement protocol, 945-954 [Zbl 1128.94303] \textit{Chen, Zhixiang; Fu, Bin}, A quadratic lower bound for Rocchio's similarity-based relevance feedback algorithm, 955-964 [Zbl 1128.68354] \textit{Böcker, Sebastian; Lipták, Zsuzsanna}, The money changing problem revisited: computing the Frobenius number in time \(O(ka_1)\), 965-974 [Zbl 1128.11057] \textit{Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge}, \(W\)-hardness under linear FPT-reductions: Structural properties and further applications, 975-984 [Zbl 1128.68362] \textit{Yang, Xiao Guang; Zhang, Jian Zhong}, Some new results on inverse sorting problems, 985-992 [Zbl 1128.68351]