Discrete Applied Mathematics, Volume 154

Volume 154, Number 1, 1 January 2006

Communications

• 
  Brian C. Dean:
  A simple expected running time analysis for randomized "divide and conquer" algorithms. 1-5
• 
  Michael J. Laszlo, Sumitra Mukherjee:
  A class of heuristics for the constrained forest problem. 6-14

Contributions

• 
  Chandra Chekuri, Guy Even, Guy Kortsarz:
  A greedy approximation algorithm for the group Steiner problem. 15-34
• 
  Marie-Christine Costa, Dominique de Werra, Christophe Picouleau:
  Using graphs for some discrete tomography problems. 35-46
• 
  Dominique de Werra, Tínaz Ekim, C. Raess:
  Construction of sports schedules with multiple venues. 47-58
• 
  Jean E. Dunbar, David J. Erwin, Teresa W. Haynes, Sandra Mitchell Hedetniemi, Stephen T. Hedetniemi:
  Broadcasts in graphs. 59-75
• 
  Ruo-Wei Hung, Maw-Shang Chang:
  Solving the path cover problem on circular-arc graphs by using an approximation algorithm. 76-105
• 
  Huiqing Liu, Mei Lu, Feng Tian:
  Trees of extremal connectivity index. 106-119
• 
  Christophe Meyer, Brigitte Jaumard:
  Equivalence of some LP-based lower bounds for the Golomb ruler problem. 120-144
• 
  Weigen Yan, Fuji Zhang:
  Enumeration of perfect matchings of a type of Cartesian products of graphs. 145-157

Notes

• 
  Ivo Blöchliger, Dominique de Werra:
  Locally restricted colorings. 158-165
• 
  Ko-Wei Lih, Chen-Ying Lin, Li-Da Tong:
  On an interpolation property of outerplanar graphs. 166-172

Volume 154, Number 2, 1 February 2006

Coding and Cryptography

• 
  Pascale Charpin, Gregory Kabatianski:
  Special Issue on Coding and Cryptography. 173
• 
  Jan Camenisch, Maciej Koprowski:
  Fine-grained forward-secure signature schemes without random oracles. 175-188
• 
  Sébastien Canard, Berry Schoenmakers, Martijn Stam, Jacques Traoré:
  List signature schemes. 189-201
• 
  Anne Canteaut, Magnus Daum, Hans Dobbertin, Gregor Leander:
  Finding nonnormal bent functions. 202-218
• 
  Paolo D'Arco, Wataru Kishimoto, Douglas R. Stinson:
  Properties and constraints of cheating-immune secret sharing schemes. 219-233
• 
  Alfredo De Santis, Anna Lisa Ferrara, Barbara Masucci:
  Unconditionally secure key assignment schemes. 234-252
• 
  Ilya Dumer, Kirill Shabunov:
  Recursive error correction for general Reed-Muller codes. 253-269
• 
  Régis Dupont, Andreas Enge:
  Provably secure non-interactive key distribution based on pairings. 270-276
• 
  Sandy Ferret, Leo Storme:
  A classification result on weighted {deltav_µ+1, deltav_µ;N, p³}-minihypers. 277-293
• 
  Jürgen Freudenberger, Victor V. Zyablov:
  On the complexity of suboptimal decoding for list and decision feedback schemes. 294-304
• 
  Ernst M. Gabidulin, Nina I. Pilipchuk:
  Symmetric matrices and codes correcting rank errors beyond the [(d-1)/2] bound. 305-312
• 
  Xiang-dong Hou:
  Affinity of permutations of P₂ⁿ. 313-325
• 
  Eike Kiltz, Arne Winterhof:
  Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem. 326-336
• 
  Alexey S. Kuzmin, Viktor T. Markov, Alexander A. Nechaev, A. S. Neljubin:
  A generalization of the binary Preparata code. 337-345
• 
  San Ling, Chaoping Xing, Ferruh Özbudak:
  An explicit class of codes with good parameters and their duals. 346-356
• 
  Subhamoy Maitra, Enes Pasalic:
  A Maiorana-McFarland type construction for resilient Boolean functions on n variables (n even) with nonlinearity >2^n-1-2^n/2+2^n/2-2. 357-369
• 
  Ueli M. Maurer:
  Secure multi-party computation made simple. 370-381
• 
  Tommi Meskanen, Ari Renvall:
  A wrap error attack against NTRUEncrypt. 382-391
• 
  Ronan Quarez:
  Some subsets of points in the plane associated to truncated Reed-Muller codes with good parameters. 392-398
• 
  John A. Ryan, Patrick Fitzpatrick:
  Enumeration of inequivalent irreducible Goppa codes. 399-412
• 
  Ana Salagean:
  Repeated-root cyclic and negacyclic codes over a finite chain ring. 413-419
• 
  Hervé Sibert, Patrick Dehornoy, Marc Girault:
  Entity authentication schemes using braid word reduction. 420-436

Volume 154, Number 3, 1 March 2006

Communications

• 
  Peter Butkovic, Karel Zimmermann:
  A strongly polynomial algorithm for solving two-sided linear systems in max-algebra. 437-446
• 
  Vesa Halava, Tero Harju, Mika Hirvensalo:
  Positivity of second order linear recurrent sequences. 447-451

Contributions

• 
  Paola Bonizzoni, Clelia de Felice, Giancarlo Mauri, Rosalba Zizza:
  Linear splicing and syntactic monoid. 452-470
• 
  Arthur H. Busch:
  A characterization of triangle-free tolerance graphs. 471-477
• 
  Peter Damaschke:
  Randomized vs. deterministic distance query strategies for point location on the line. 478-484
• 
  Célia Picinin de Mello, Aurora Morgana, Marco Liverani:
  The clique operator on graphs with few P₄'s. 485-492
• 
  Jean Diatta:
  Description-meet compatible multiway dissimilarities. 493-507
• 
  Sun-Yuan Hsieh, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko:
  The Hamiltonian problem on distance-hereditary graphs. 508-524
• 
  Chuan-Min Lee, Maw-Shang Chang:
  Distance-hereditary graphs are clique-perfect. 525-536
• 
  Valery A. Liskovets:
  Exact enumeration of acyclic deterministic automata. 537-551
• 
  Jaume Martí-Farré, Carles Padró:
  Secret sharing schemes on access structures with intersection number equal to one. 552-563
• 
  Cécile Murat, Vangelis Th. Paschos:
  On the probabilistic minimum coloring and minimum k-coloring. 564-586

Notes

• 
  Victor J. W. Guo, Jiang Zeng:
  The number of convex polyominoes and the generating function of Jacobi polynomials. 587-593
• 
  Sonoko Moriyama, Masahiro Hachimori:
  h-Assignments of simplicial complexes and reverse search. 594-597
• 
  Wei-Fan Wang:
  The L(2, 1)-labelling of trees. 598-603

Volume 154, Number 4, 15 March 2006

Efficient Algorithms

• 
  Evripidis Bampis, Klaus Jansen:
  Introduction. 609
• 
  Leah Epstein, Rob van Stee:
  Optimal on-line flow time with resource augmentation. 611-621
• 
  Foto N. Afrati, Ioannis Milis:
  Designing PTASs for MIN-SUM scheduling problems. 622-639
• 
  Monaldo Mastrolilli, Marcus Hutter:
  Hybrid rounding techniques for knapsack problems. 640-649
• 
  Benjamin Doerr:
  Non-independent randomized rounding and coloring. 650-659
• 
  Daniel Král, Jan Kratochvíl, Andrzej Proskurowski, Heinz-Jürgen Voss:
  Coloring mixed hypertrees. 660-672
• 
  Thomas Erlebach, Danica Vukadinovic:
  Path problems in generalized stars, complete graphs, and brick wall graphs. 673-683
• 
  Taneli Mielikäinen, Esko Ukkonen:
  The complexity of maximum matroid-greedoid intersection and weighted greedoid maximization^, . 684-691

Volume 154, Number 5, 1 April 2006

IV ALIO/EURO Workshop on Applied Combinatorial Optimization

• 
  Celso C. Ribeiro:
  Preface. 693
• 
  Dario J. Aloise, Daniel Aloise, Caroline T. M. Rocha, Celso C. Ribeiro, José C. Ribeiro Filho, Luiz S. S. Moura:
  Scheduling workover rigs for onshore oil production. 695-702
• 
  Rafael Andrade, Abilio Lucena, Nelson Maculan:
  Using Lagrangian dual information to generate degree constrained spanning trees. 703-717
• 
  Jacek Blazewicz, Marta Kasprzak:
  Computational complexity of isothermic DNA sequencing by hybridization. 718-729
• 
  Alfredo Candia-Véjar, Hugo Bravo-Azlán:
  Worst-case performance of Wong's Steiner tree heuristic. 730-737
• 
  Alberto Caprara, Michele Monaci, Paolo Toth, Pier Luigi Guida:
  A Lagrangian heuristic algorithm for a real-world train timetabling problem. 738-753
• 
  Irène Charon, Olivier Hudry:
  Noising methods for a clique partitioning problem. 754-769
• 
  Pablo E. Coll, Celso C. Ribeiro, Cid C. de Souza:
  Multiprocessor scheduling under precedence constraints: Polyhedral results. 770-801
• 
  Pierre Hansen, Nenad Mladenovic:
  First vs. best improvement: An empirical study. 802-817
• 
  Lilian Markenzon, Cláudia Marcela Justel, N. Paciornik:
  Subclasses of k-trees: Characterization and recognition. 818-825
• 
  Isabel Méndez-Díaz, Paula Zabala:
  A Branch-and-Cut algorithm for graph coloring. 826-847
• 
  Nikola S. Nikolov, Alexandre Tarassov:
  Graph layering by promotion of nodes. 848-860
• 
  Nei Yoshihiro Soma, J. P. Melo:
  On irreversibility of von Neumann additive cellular automata on grids. 861-866
• 
  Andrés Weintraub, Alan T. Murray:
  Review of combinatorial problems induced by spatial forest harvesting planning. 867-879

Volume 154, Number 6, 15 April 2006

Communications

• 
  Gregory Z. Gutin, Arash Rafiey, Anders Yeo, Michael Tso:
  Level of repair analysis and minimum cost homomorphisms of graphs. 881-889
• 
  Gregory Z. Gutin, Arash Rafiey, Anders Yeo:
  Minimum cost and list homomorphisms to semicomplete digraphs. 890-897
• 
  Julien Moncel:
  Monotonicity of the minimum cardinality of an identifying code in the hypercube. 898-899

Contributions

• 
  Gautam Appa, Dimitris Magos, Ioannis Mourtos:
  A new class of facets for the Latin square polytope. 900-911
• 
  Wensong Chu, Charles J. Colbourn, Peter Dukes:
  On constant composition codes. 912-929
• 
  Beiliang Du:
  Existence of resolvable optimal strong partially balanced designs. 930-941
• 
  Keqin Feng:
  Unextendible product bases and 1-factorization of complete graphs. 942-949
• 
  Satoru Fujishige, Akihisa Tamura:
  A general two-sided matching market with discrete concave utility functions. 950-970
• 
  Refael Hassin, Shlomi Rubinstein:
  An approximation algorithm for maximum triangle packing. 971-979
• 
  Reinhard C. Laubenbacher, Bodo Pareigis:
  Update schedules of sequential dynamical systems. 980-994
• 
  Dániel Marx:
  Precoloring extension on unit interval graphs. 995-1002
• 
  Sheng-Lung Peng, Chi-Kang Chen:
  On the interval completion of chordal graphs. 1003-1010
• 
  Zhao Zhang, Jixiang Meng:
  On optimally-lambda⁽³⁾ transitive graphs. 1011-1018

Notes

• 
  T. C. Edwin Cheng, Yaojun Chen, C. T. Ng:
  A note on acyclic domination number in graphs of diameter two. 1019-1022
• 
  Michael Dorfling, Michael A. Henning:
  A note on power domination in grid graphs. 1023-1027
• 
  Grzegorz Malewicz:
  Latin squares with bounded size of row prefix intersections. 1028-1031
• 
  Lorenzo Traldi:
  On the colored Tutte polynomial of a graph of bounded treewidth. 1032-1036

Volume 154, Number 7, 1 May 2006

Discrete Mathematics and Data Mining II (DM and DM II)

• 
  Martin Anthony, Endre Boros, Peter L. Hammer, Alexander Kogan:
  Preface. 1037
• 
  Gabriela Alexe, Peter L. Hammer:
  Spanned patterns for the logical analysis of data. 1039-1049
• 
  Sorin Alexe, Peter L. Hammer:
  Accelerated algorithm for pattern detection in logical analysis of data. 1050-1063
• 
  Anne Berry, Eric SanJuan, Alain Sigayret:
  Generalized domination in closure systems. 1064-1084
• 
  François Brucker:
  Sub-dominant theory in numerical taxonomy. 1085-1099
• 
  Rajeev Kohli, Ramesh Krishnamurti, Kamel Jedidi:
  Subset-conjunctive rules for breast cancer diagnosis. 1100-1112
• 
  Taneli Mielikäinen:
  Frequency-based views to pattern collections. 1113-1139
• 
  Jutta Gebert, Martin Lätsch, Stefan Wolfgang Pickl, Gerhard-Wilhelm Weber, Röbbe Wünschiers:
  An algorithm to analyze stability of gene-expression patterns. 1140-1156

Volume 154, Number 8, 15 May 2006

Contributions

• 
  Vitaly I. Voloshin, Heinz-Jürgen Voss:
  Circular mixed hypergraphs II: The upper chromatic number. 1157-1172
• 
  Wensong Lin, Jianzhuan Wu, Peter Che Bor Lam, Guohua Gu:
  Several parameters of generalized Mycielskians. 1173-1182
• 
  Qing-Hu Hou, Toufik Mansour:
  Horse paths, restricted 132-avoiding permutations, continued fractions, and Chebyshev polynomials. 1183-1197
• 
  Dariusz Dereniowski:
  Edge ranking of weighted trees. 1198-1209
• 
  Petr Hlinený:
  Equivalence-free exhaustive generation of matroid representations. 1210-1222
• 
  T. Bornand-Jaccard, David Schindl, Dominique de Werra:
  Some simple optimization techniques for self-organized public key management in mobile ad hoc networks. 1223-1235
• 
  Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten:
  The satisfactory partition problem. 1236-1245
• 
  Irène Charon, Sylvain Gravier, Olivier Hudry, Antoine Lobstein, Michel Mollard, Julien Moncel:
  A linear algorithm for minimum 1-identifying codes in oriented trees. 1246-1253
• 
  Hiroshi Nagamochi, Taizo Kawada:
  Minmax subtree cover problem on cacti. 1254-1263
• 
  Rahul Santhanam, Kamala Krithivasan:
  Graph splicing systems. 1264-1278
• 
  Yuuki Tanaka, Yukio Shibata:
  On the pagenumber of trivalent Cayley graphs. 1279-1292
• 
  Teresa W. Haynes, Michael A. Henning, Jamie Howard:
  Locating and total dominating sets in trees. 1293-1300

Notes

• 
  James Mc Laughlin, Nancy J. Wyshinski:
  Further combinatorial identities deriving from the nth power of a 2×2 matrix. 1301-1308
• 
  T. S. Michael, Thomas Quint:
  Sphericity, cubicity, and edge clique covers of graphs. 1309-1313

Volume 154, Number 9, June 2006

2nd Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2003)

• 
  Ulrich Faigle, Johann L. Hurink, Stefan Wolfgang Pickl:
  Preface. 1315
• 
  Stephan Dominique Andres:
  The game chromatic index of forests of maximum degree Delta>=5. 1317-1323
• 
  Gabriela R. Argiroffo, Silvia M. Bianchi, Graciela L. Nasini:
  Clutter nonidealness. 1324-1334
• 
  Paul S. Bonsma, Thomas Epping, Winfried Hochstättler:
  Complexity results on restricted instances of a paint shop problem for words. 1335-1343
• 
  Maurizio Bruglieri, Matthias Ehrgott, Horst W. Hamacher, Francesco Maffioli:
  An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints. 1344-1357
• 
  Gruia Calinescu, Sanjiv Kapoor, Mohammad Sarwat:
  Bounded-hops power assignment in ad hoc wireless networks. 1358-1371
• 
  Aneta Dudek, Gyula Y. Katona, A. Pawel Wojda:
  Hamiltonian path saturated graphs with small size. 1372-1379
• 
  Ulrich Faigle, Gereon Frahling:
  A combinatorial algorithm for weighted stable sets in bipartite graphs. 1380-1391
• 
  Toshihiro Fujito, Tsuyoshi Okumura:
  A modified greedy algorithm for dispersively weighted 3-set cover. 1392-1400
• 
  Francesco Maffioli, Norma Zagaglia Salvi:
  On some properties of base-matroids. 1401-1407
• 
  Arnaud Pêcher, Annegret Wagler:
  On non-rank facets of stable set polytopes of webs with clique number four. 1408-1415
• 
  Bert Randerath, Preben D. Vestergaard:
  Well-covered graphs and factors. 1416-1428
• 
  A. N. M. Salman, Hajo Broersma:
  Path-fan Ramsey numbers. 1429-1436
• 
  Lutz Volkmann, Stefan Winzen:
  On the connectivity of close to regular multipartite tournaments. 1437-1452
• 
  Liming Xiong, Hajo Broersma:
  Subpancyclicity of line graphs and degree sums along paths. 1453-1463

Volume 154, Number 10, June 2006

• 
  Martin Charles Golumbic, Aviad Mintz, Udi Rotics:
  Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial k-trees. 1465-1477
• 
  Jonathan K. Hodge:
  Permutations of separable preference orders. 1478-1499
• 
  Christos Kaklamanis, Danny Krizanc, Manuela Montangero, Giuseppe Persiano:
  Efficient automatic simulation of parallel computation on networks of workstations. 1500-1509
• 
  Jörn Quistorff:
  New upper bounds on Lee codes. 1510-1521
• 
  Christopher Schwarz, Denise Sakai Troxell:
  L(2, 1)-labelings of Cartesian products of two cycles. 1522-1540

Notes

• 
  Baogen Xu:
  Two classes of edge domination in graphs. 1541-1546

Volume 154, Number 11, July 2006

• 
  Klaus Holzapfel, Sven Kosub, Moritz G. Maaß, Hanjo Täubig:
  The complexity of detecting fixed-density clusters. 1547-1562
• 
  Joan Hutchinson, André Kündgen:
  Orthogonal art galleries with interior walls. 1563-1569
• 
  Dimitri Kagaris:
  A similarity transform for linear finite state machines. 1570-1577
• 
  Ton Kloks, Dieter Kratsch, Chuan-Min Lee, Jiping Liu:
  Improved bottleneck domination algorithms. 1578-1592
• 
  Toufik Mansour, Eva Yu-Ping Deng, Rosena R. X. Du:
  Dyck paths and restricted permutations. 1593-1605
• 
  Huifang Miao, Xiaofeng Guo:
  Lower and upper orientable strong radius and strong diameter of complete k-partite graphs. 1606-1614
• 
  Young-Soo Myung:
  Multicommodity flows in cycle graphs. 1615-1621
• 
  Zhizheng Zhang, Jun Wang:
  Bernoulli matrix and its algebraic properties. 1622-1632

Notes

• 
  Stephen G. Hartke:
  The elimination procedure for the competition number is not optimal. 1633-1639
• 
  Wenjun Xiao:
  Some results on diameters of Cayley graphs. 1640-1644

Errata

• 
  Eckhard Steffen, Tomaz Pisanski, Marko Boben, Natasa Ravnik:
  Erratum to "Reduction of symmetric configurations n₃" [Discrete Appl. Math. 99 (1-3) (2000) 401 -411]. 1645-1646

Volume 154, Number 12, July 2006

• 
  R. Julian R. Abel, Norman J. Finizio, Gennian Ge, Malcolm Greig:
  New Z-cyclic triplewhist frames and triplewhist tournament designs. 1649-1673
• 
  Eyal Ackerman, Gill Barequet, Ron Y. Pinter:
  A bijection between permutations and floorplans, and its applications. 1674-1684
•