Information Processing Letters, Volume 97

Volume 97, Number 1, 16 January 2006

• Feifeng Zheng, Francis Y. L. Chin, Stanley P. Y. Fung, Chung Keung Poon, Yinfeng Xu:
  A tight lower bound for job scheduling with cancellation. 1-3
  
• Xiaotie Deng, Li-Sha Huang:
  On the complexity of market equilibria with maximum social welfare. 4-11
  
• Amos Beimel, Enav Weinreb:
  Monotone circuits for monotone weighted threshold functions. 12-18
  
• Oswin Aichholzer, Franz Aurenhammer, Clemens Huemer, Hannes Krasser:
  Transforming spanning trees and pseudo-triangulations. 19-22
  
• Haim Kaplan, Nira Shafrir:
  The greedy algorithm for edit distance with moves. 23-27
  
• Bolette Ammitzbøll Madsen:
  An algorithm for Exact Satisfiability analysed with the number of clauses as parameter. 28-30
  
• Uriel Feige, Daniel Reichman:
  On the hardness of approximating Max-Satisfy. 31-35
  
• Salvatore Caporaso:
  A decidable characterization of the classes between lintime and exptime. 36-40
  

Volume 97, Number 2, 31 January 2006

• Jacques Dubrois, Jean-Guillaume Dumas:
  Efficient polynomial time algorithms computing industrial-strength primitive roots. 41-45
  
• René Vestergaard:
  A constructive approach to sequential Nash equilibria. 46-51
  
• Mitsugu Iwamoto, Hirosuke Yamamoto:
  Strongly secure ramp secret sharing schemes for general access structures. 52-57
  
• Christel Baier, Nathalie Bertrand, Ph. Schnoebelen:
  A note on the attractor-property of infinite-state Markov chains. 58-63
  
• Wen-Hung Kuo, Dar-Li Yang:
  Minimizing the makespan in a single machine scheduling problem with a time-based learning effect. 64-67
  
• Marek Chrobak, Claire Kenyon, Neal E. Young:
  The reverse greedy algorithm for the metric k-median problem. 68-72
  
• Guohui Lin, Zhipeng Cai, Dekang Lin:
  Vertex covering by paths on trees with its applications in machine translation. 73-81
  

Volume 97, Number 3, 14 February 2006

• Sangwon Kim, Joonwon Lee, Jinsoo Kim:
  Runtime feasibility check for non-preemptive real-time periodic tasks. 83-87
  
• Xiaofan Yang, Jianqiu Cao, Graham M. Megson, Jun Luo:
  Minimum neighborhood in a generalized cube. 88-93
  
• Jun-Ming Xu, Meijie Ma, Min Lü:
  Paths in Möbius cubes and crossed cubes. 94-97
  
• Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos:
  Weighted Coloring: further complexity and approximability results. 98-103
  
• Srecko Brlek, Sardaouna Hamadou, John Mullins:
  A flaw in the electronic commerce protocol SET. 104-108
  
• Jiong Guo, Rolf Niedermeier:
  A fixed-parameter tractability result for multicommodity demand flow in trees. 109-114
  
• Wenjun Xiao, Behrooz Parhami:
  Cayley graphs as models of deterministic small-world networks. 115-117
  
• Jung Hee Cheon, Woo-Hwan Kim, Hyun Soo Nam:
  Known-plaintext cryptanalysis of the Domingo-Ferrer algebraic privacy homomorphism scheme. 118-123
  
• Yuan Li, Thomas W. Cusick:
  Linear structures of symmetric functions over finite fields. 124-127
  

Volume 97, Number 4, 28 February 2006

• Pak Ching Li, Michel Toulouse:
  Variations of the maximum leaf spanning tree problem for bipartite graphs. 129-132
  
• Travis Gagie:
  Compressing probability distributions. 133-137
  
• Zhenming Chen, Evanthia Papadopoulou, Jinhui Xu:
  Robustness of k-gon Voronoi diagram construction. 138-145
  
• Zheng Sun, Tian-Ming Bu:
  On discretization methods for approximating optimal paths in regions with direction-dependent costs. 146-152
  
• Hossein Ghodosi, Rahim Zaare-Nahandi:
  Comments on the 'm out of n oblivious transfer'. 153-155
  
• Mohammad Taghi Hajiaghayi, Harald Räcke:
  An O(sqrt(n))-approximation algorithm for directed sparsest cut. 156-160
  
• Neal Lesh, Michael Mitzenmacher:
  BubbleSearch: A simple heuristic for improving priority-based greedy algorithms. 161-169
  

Volume 97, Number 5, 16 March 2006

• Yves F. Verhoeven:
  Enhanced algorithms for Local Search. 171-176
  
• Adam Kasperski, Pawel Zielinski:
  An approximation algorithm for interval data minmax regret combinatorial optimization problems. 177-180
  
• Pavlos Efraimidis, Paul G. Spirakis:
  Weighted random sampling with a reservoir. 181-185
  
• Morteza Fayyazi, David R. Kaeli, Waleed Meleis:
  An adjustable linear time parallel algorithm for maximum weight bipartite matching. 186-190
  
• Fedor V. Fomin, Kjartan Høie:
  Pathwidth of cubic graphs and exact algorithms. 191-196
  
• Ewa Misiolek, Danny Z. Chen:
  Two flow network simplification algorithms. 197-202
  
• Kang Li, Lusheng Wang:
  A polynomial time approximation scheme for embedding a directed hypergraph on a ring. 203-207
  
• Mark Adcock, Richard Cleve, Kazuo Iwama, Raymond H. Putra, Shigeru Yamashita:
  Quantum lower bounds for the Goldreich-Levin problem. 208-211
  

Volume 97, Number 6, 31 March 2006

• Stéphanie Delaune:
  Easy intruder deduction problems with homomorphisms. 213-218
  
• Bo Gyeong Kang, Je Hong Park:
  On the relationship between squared pairings and plain pairings. 219-224
  
• Nicolas Markey, Ph. Schnoebelen:
  Mu-calculus path checking. 225-230
  
• Mirela Damian, Sriram V. Pemmaraju:
  APX-hardness of domination problems in circle graphs. 231-237
  
• Jeng Farn Lee, Meng Chang Chen, Ming-Tat Ko, Wanjiun Liao:
  Bandwidth allocation algorithms for weighted maximum rate constrained link sharing policy. 238-243
  
• Dungjade Shiowattana, Satyanarayana V. Lokam:
  An optimal lower bound for 2-query locally decodable linear codes. 244-250
  

Last update Fri May 25 09:27:28 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page