Discrete Applied Mathematics, Volume 155

Volume 155, Number 1, January 2007

• 
  Bernard Ries:
  Coloring some classes of mixed graphs. 1-6

Contributions

• 
  Manuel de la Sen, Asier Ibeas:
  On the stability properties of linear dynamic time-varying unforced systems involving switches between parameterizations from topologic considerations via graph theory. 7-25
• 
  Jean-Luc Marichal, Ivan Kojadinovic, Katsushige Fujimoto:
  Axiomatic characterizations of generalized values. 26-43
• 
  András Recski, Dávid Szeszlér:
  Routing vertex disjoint Steiner-trees in a cubic grid and connections to VLSI. 44-52
• 
  Michael Soltys:
  The proof theoretic strength of the Steinitz exchange theorem. 53-60
• 
  Maria Isabel Gonzalez Vasco, David Pérez-García:
  Attacking a public key cryptosystem based on tree replacement. 61-67

Notes

• 
  Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg:
  Finite metrics in switching classes. 68-73
• 
  Baogang Xu, Haihui Zhang:
  Every toroidal graph without adjacent triangles is (4, 1)^*-choosable. 74-78

Volume 155, Number 2, January 2007

29th Symposium on Mathematical Foundations of Computer Science MFCS 2004

• 
  Jan Kratochvíl, Josep Díaz, Jirí Fiala:
  Editorial. 79-80
• 
  Zeev Nutov, Raphael Yuster:
  Packing directed cycles efficiently. 82-91
• 
  Hajo Broersma, Fedor V. Fomin, Rastislav Kralovic, Gerhard J. Woeginger:
  Eliminating graphs by means of parallel knock-out schemes. 92-102
• 
  Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski, Rahul Tripathi:
  Complexity results in graph reconstruction. 103-118
• 
  Ioannis Caragiannis, Aleksei V. Fishkin, Christos Kaklamanis, Evi Papaioannou:
  Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs. 119-136
• 
  Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino:
  Enumerating disjunctions and conjunctions of paths and cuts in reliability theory. 137-149
• 
  Robert Elsässer, Ulf Lorenz, Thomas Sauerwald:
  Agent-based randomized broadcasting in large networks. 150-160
• 
  Nadine Baumann, Ekkehard Köhler:
  Approximating earliest arrival flows with flow-dependent transit times. 161-171
• 
  Miroslav Chlebík, Janka Chlebíková:
  Minimum 2SAT-DELETION: Inapproximability results and relations to Minimum Vertex Cover. 172-179
• 
  Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia:
  Polynomial time approximation schemes and parameterized complexity. 180-193
• 
  André Gronemeier:
  Approximating Boolean functions by OBDDs. 194-209
• 
  Henrik Björklund, Sergei G. Vorobyov:
  A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. 210-229
• 
  Hans-Joachim Böckenhauer, Dirk Bongartz:
  Protein folding in the HP model on grid lattices with diagonals. 230-256

Volume 155, Number 3, February 2007

• 
  José R. Correa, Samuel Fiorini, Nicolás E. Stier Moses:
  A note on the precedence-constrained class sequencing problem. 257-259

Contributions

• 
  Omran Ahmadi, Darrel Hankerson, Alfred Menezes:
  Formulas for cube roots in F_3^m. 260-270
• 
  Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, Clemens Huemer:
  Connecting colored point sets. 271-278
• 
  Francine Blanchet-Sadri, Arundhati R. Anavekar:
  Testing primitivity on partial words. 279-287
• 
  Ferdinando Cicalese, Peter Damaschke, Libertad Tansini, Sören Werth:
  Overlaps help: Improved bounds for group testing with interval queries. 288-299
• 
  Antonio Fernández, Tom Leighton, José Luis López-Presa:
  Containment properties of product and power graphs. 300-311
• 
  Philippe Galinier, Alain Hertz:
  Solution techniques for the Large Set Covering Problem. 312-326
• 
  Petr Kolman, Tomasz Walen:
  Approximating reversal distance for strings with bounded number of duplicates. 327-336
• 
  Christian Liebchen, Romeo Rizzi:
  Classes of cycle bases. 337-355
• 
  Ortrud R. Oellermann, Joel Peters-Fransen:
  The strong metric dimension of graphs and digraphs. 356-364
• 
  Alan P. Sprague:
  O(1) query time algorithm for all pairs shortest distances on permutation graphs. 365-373
• 
  László A. Székely, Hua Wang:
  Binary trees with the largest number of subtrees. 374-385
• 
  Boaz Tsaban:
  Decompositions of graphs of functions and fast iterations of lookup tables. 386-393

Notes

• 
  Faryad Ali:
  On the ranks of O'N and Ly. 394-399
• 
  Guantao Chen, Richard H. Schelp:
  Decomposition of bipartite graphs into special subgraphs. 400-404
• 
  Yuanqiu Huang, Yuming Chu:
  A note on the computational complexity of graph vertex partition. 405-409
• 
  Vladimir Nikiforov, Richard H. Schelp:
  Making the components of a graph k-connected. 410-415
• 
  Xiangtong Qi:
  A note on worst-case performance of heuristics for maintenance scheduling problems. 416-422
• 
  Bhalchandra D. Thatte:
  A correct proof of the McMorris-Powers' theorem on the consensus of phylogenies. 423-427

Volume 155, Number 4, February 2007

• 
  Moncef Abbas, Marc Pirlot, Philippe Vincke:
  Tangent circle graphs and 'orders'. 429-441
• 
  Jørgen Bang-Jensen, Jing Huang, Louis Ibarra:
  Recognizing and representing proper interval graphs in parallel using merging and sorting. 442-456
• 
  Sergey Bereg, Hao Wang:
  Wiener indices of balanced binary trees. 457-467
• 
  Valentin E. Brimkov, David Coeurjolly, Reinhard Klette:
  Digital planarity - A review. 468-495
• 
  Francesc Carreras:
  Automorphisms and blocking in simple games. 496-505
• 
  Tomás Dvorák:
  Dense sets and embedding binary trees into hypercubes. 506-514
• 
  Mohamed H. El-Zahar, Soheir M. Khamis, Khalida Mohammad Nazzal:
  On the domination number of the cartesian product of the cycle of length n and any graph. 515-522
• 
  Hiroshi Nagamochi, Yuusuke Abe:
  An approximation algorithm for dissecting a rectangle into rectangles with specified areas. 523-537
• 
  Nigel P. Smart, Frederik Vercauteren:
  On computable isomorphisms in efficient asymmetric pairing-based systems. 538-547
• 
  Robin Strand, Benedek Nagy:
  Distances based on neighbourhood sequences in non-standard three-dimensional grids. 548-557
• 
  Manouchehr Zaker:
  Maximum transversal in partial Latin squares and rainbow matchings. 558-565

Notes

• 
  Ting Chen, Frank K. Hwang:
  A competitive algorithm in searching for many edges in a hypergraph. 566-571
• 
  Refael Hassin, Asaf Levin:
  Flow trees for vertex-capacitated networks. 572-578
• 
  Mohit Singh, Amitabha Tripathi:
  On an extremal problem related to a theorem of Whitney. 579-583

Volume 155, Number 5, March 2007

• 
  C. N. Campos, Célia Picinin de Mello:
  A result on the total colouring of powers of cycles. 585-597
• 
  Tamar Eilam, Cyril Gavoille, David Peleg:
  Average stretch analysis of compact routing schemes. 598-610
• 
  Martin Gavalec, Ján Plávka:
  Simple image set of linear mappings in a max-min algebra. 611-622
• 
  David Pisinger:
  The quadratic knapsack problem - a survey. 623-648

Notes

• 
  Piotr Berman, Marek Karpinski, Alexander D. Scott:
  Computational complexity of some restricted instances of 3-SAT. 649-653
• 
  Haiyan Chen, Fuji Zhang:
  Resistance distance and the normalized Laplacian spectrum. 654-661
• 
  Hong-Bin Chen, Frank K. Hwang:
  Exploring the missing link among d-separable, d^_-separable and d-disjunct matrices. 662-664
• 
  Qingshu Meng, Huanguo Zhang, Min Yang, Jingsong Cui:
  On the degree of homogeneous bent functions. 665-669
• 
  Amitabha Tripathi, Sujith Vijay:
  A short proof of a theorem on degree sets of graphs. 670-671

Volume 155, Numbers 6-7, April 2007

Computational Molecular Biology Series, Issue V

• 
  Sorin Istrail, Pavel A. Pevzner, Ron Shamir:
  Preface. 673-674
• 
  Tatsuya Akutsu, Hideo Bannai, Satoru Miyano, Sascha Ott:
  On the complexity of deriving position specific score matrices from positive and negative sequences. 676-685
• 
  Liliana Alcón, Márcia R. Cerioli, Celina M. H. de Figueiredo, Marisa Gutierrez, João Meidanis:
  Tree loop graphs. 686-694
• 
  Alberto Apostolico, Cinzia Pizzi:
  Motif discovery by monotone scores. 695-706
• 
  Nikhil Bansal, Mark Cieliebak, Zsuzsanna Lipták:
  Finding submasses in weighted strings with Fast Fourier Transform. 707-718
• 
  Piotr Berman, Bhaskar DasGupta, Dhruv Mubayi, Robert H. Sloan, György Turán, Yi Zhang:
  The inverse protein folding problem on 2D and 3D lattices. 719-732
• 
  Piotr Berman, Bhaskar DasGupta, Eduardo D. Sontag:
  Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. 733-749
• 
  Benny Chor, Michael D. Hendy, David Penny:
  Analytic solutions for three taxon ML trees with variable rates across sites. 750-758
• 
  Peter Clote, Evangelos Kranakis, Danny Krizanc, Ladislav Stacho:
  Asymptotic expected number of base pairs in optimal secondary structure for random RNA using the Nussinov-Jacobson energy model. 759-787
• 
  Jens Gramm, Till Nierhoff, Roded Sharan, Till Tantau:
  Haplotyping with missing data via perfect path phylogenies. 788-805
• 
  Dan Gusfield, Dean Hickerson, Satish Eddhu:
  An efficiently computed lower bound on the number of recombinations in phylogenetic networks: Theory and empirical study. 806-830
• 
  Oliver D. King, Philippe Gaborit:
  Binary templates for comma-free DNA codes. 831-839
• 
  Gunnar W. Klau, Sven Rahmann, Alexander Schliep, Martin Vingron, Knut Reinert:
  Integer linear programming approaches for non-unique probe selection. 840-856
• 
  Steven Skiena, Sagi Snir:
  Restricting SBH ambiguity via restriction enzymes. 857-867
• 
  Valery T. Stefanov, Stéphane Robin, Sophie Schbath:
  Waiting times for clumps of patterns and for structured motifs in random sequences. 868-880
• 
  Eric Tannier, Anne Bergeron, Marie-France Sagot:
  Advances on sorting by reversals. 881-888

Volume 155, Number 8, April 2007

• 
  Stavros G. Kolliopoulos, George Steiner:
  Partially ordered knapsack and applications to scheduling. 889-897
• 
  Gianluca De Marco, Marco Pellegrini, Giovanni Sburlati:
  Faster deterministic wakeup in multiple access channels. 898-903
• 
  Kejun Chen, Ruizhong Wei:
  Super-simple (v, 5, 4) designs. 904-913
• 
  Magnus Bordewich, Charles Semple:
  Computing the minimum number of hybridization events for a consistent evolutionary history. 914-928
• 
  Sergey Kitaev:
  Introduction to partially ordered patterns. 929-944
• 
  Joseph Y.-T. Leung, Haibing Li, Michael L. Pinedo:
  Scheduling orders for multiple product types to minimize total weighted completion time. 945-970
• 
  Seog-Jin Kim, Suh-Ryung Kim, Yoomi Rho:
  On CCE graphs of doubly partial orders. 971-978
• 
  Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten:
  Efficient algorithms for decomposing graphs under degree constraints. 979-988
• 
  Elizabeth Goode, Dennis Pixton:
  Recognizing splicing languages: Syntactic monoids and simultaneous pumping. 989-1006
• 
  Gerard J. Chang, Jer-Jeong Chen, David Kuo, Sheng-Chyang Liaw:
  Distance-two labelings of digraphs. 1007-1013
• 
  Chiara Epifanio, Filippo Mignosi, Jeffrey O. Shallit, Ilaria Venturini:
  On Sturmian graphs. 1014-1030
• 
  Sunghyu Han, June Bok Lee:
  Nonexistence of near-extremal formally self-dual even codes of length divisible by 8. 1031-1037
• 
  Jiping Liu, Yuejian Peng, Cheng Zhao:
  Characterization of P₆-free graphs. 1038-1043
• 
  Yumei Hu, Xueliang Li, Yongtang Shi, Tianyi Xu:
  Connected (n, m)-graphs with minimum and maximum zeroth-order general Randic index. 1044-1054
• 
  Brian Lucena:
  Achievable sets, brambles, and sparse treewidth obstructions. 1055-1065

Notes

• 
  A. M. Youssef:
  Generalized hyper-bent functions over GF(p). 1066-1070
• 
  W. Kook:
  Edge-rooted forests and the alpha-invariant of cone graphs. 1071-1075

Volume 155, Number 9, May 2007

Advances in Graph Drawing: The 11th International Symposium on Graph Drawing,

• 
  Giuseppe Liotta, Henk Meijer:
  Advances in graph drawing: The 11th International Symposium on Graph Drawing. 1077
• 
  Hubert de Fraysseix, Patrice Ossona de Mendez:
  Barycentric systems and stretchability. 1079-1095
• 
  Jakub Cerný, Zdenek Dvorák, Vít Jelínek, Jan Kára:
  Noncrossing Hamiltonian paths in geometric graphs. 1096-1105
• 
  Farhad Shahrokhi, Ondrej Sýkora, László A. Székely, Imrich Vrto:
  On k-planar crossing numbers. 1106-1115
• 
  Ashim Garg, Adrian Rusu:
  Area-efficient planar straight-line drawings of outerplanar graphs. 1116-1140
• 
  Toru Hasunuma:
  Queue layouts of iterated line directed graphs. 1141-1154
• 
  Hiroshi Nagamochi, Katsutoshi Kuroya:
  Drawing c-planar biconnected clustered graphs. 1155-1174

Volume 155, Number 10, May 2007

• 
  Arnold Knopfmacher, Robert F. Tichy, Stephan G. Wagner, Volker Ziegler:
  Graphs, partitions and Fibonacci numbers. 1175-1187
• 
  Ma-Lian Chia, David Kuo, Mei-Feng Tung:
  The multiple originator broadcasting problem in graphs. 1188-1199
• 
  Wen-Qing Xu, Solomon W. Golomb:
  Optimal interleaving schemes for correcting two-dimensional cluster errors. 1200-1212
• 
  Bang Ye Wu, Hung-Lung Wang, Shih Ta Kuan, Kun-Mao Chao:
  On the uniform edge-partition of a tree. 1213-1223
• 
  Kazuyuki Amano, Akira Maruoka:
  Better upper bounds on the QOBDD size of integer multiplication. 1224-1232
• 
  Dieter Rautenbach, Christian Szegedy, Jürgen Werber:
  The delay of circuits whose inputs have specified arrival times. 1233-1243
• 
  Abdo Y. Alfakih:
  On dimensional rigidity of bar-and-joint frameworks. 1244-1253
• 
  Ligong Wang, Hajo Broersma, Cornelis Hoede, Xueliang Li, Georg Still:
  Integral trees of diameter 6. 1254-1266
• 
  Zemin Jin, Huifang Yan, Qinglin Yu:
  Generalization of matching extensions in graphs (II). 1267-1274
• 
  Dekel Tsur:
  Tree-edges deletion problems with bounded diameter obstruction sets. 1275-1293
• 
  Tomislav Doslic, Damir Vukicevic:
  Computing the bipartite edge frustration of fullerene graphs. 1294-1301
• 
  Changhong Lu, Lei Chen, Mingqing Zhai:
  Extremal problems on consecutive L(2, 1)-labelling. 1302-1313
• 
  Sarah Spence Adams, Jonathan Cass, Matthew Tesch, Denise Sakai Troxell, Cody Wheeland:
  The minimum span of L(2, 1)-labelings of certain generalized Petersen graphs. 1314-1325
• 
  Roberto Cordone:
  A subexponential algorithm for the coloured tree partition problem. 1326-1335
• 
  Douglas Bauer, Hajo Broersma, Nathan Kahl, Aurora Morgana, Edward F. Schmeichel, Thomas M. Surowiec:
  Tutte sets in graphs II: The complexity of finding maximum Tutte sets. 1336-1343

Volume 155, Number 11, June 2007

• 
  Peter Ladislaw Hammer: December 23, 1936 to December 27, 2006. 1345-1347

Contributions

• 
  Hans L. Bodlaender, Arie M. C. A. Koster:
  On the maximum cardinality search lower bound for treewidth. 1348-1372
• 
  Nir Halman, Shmuel Onn, Uriel G. Rothblum:
  The convex dimension of a graph. 1373-1383
• 
  Peter Hamburger, Robert C. Vandell, Matt Walsh:
  Routing sets in the integer lattice. 1384-1394
• 
  Csilla Bujtás, Zsolt Tuza:
  Orderings of uniquely colorable hypergraphs. 1395-1407
• 
  Stefan Porschen, Ewald Speckenmeyer:
  Satisfiability of mixed Horn formulas. 1408-1419
• 
  Mirko Hornák, Zsolt Tuza, Mariusz Wozniak:
  On-line arbitrarily vertex decomposable trees. 1420-1429
• 
  Toufik Mansour, Vincent Vajnovszki:
  Restricted 123-avoiding Baxter permutations and the Padovan numbers. 1430-1440
• 
  Toshimasa Ishii, Kengo Iwata, Hiroshi Nagamochi:
  Bisecting a 4-connected graph with three resource sets. 1441-1450
• 
  Axel Kohnert:
  Constructing two-weight codes with prescribed groups of automorphisms. 1451-1457
• 
  Feodor F. Dragan, Irina Lomonosov:
  On compact and efficient routing in certain graph classes. 1458-1470
• 
  Yusuke Kobayashi, Kazuo Murota:
  Induction of M-convex functions by linking systems. 1471-1480
• 
  Miklós Bóna, Hyeong-Kwan Ju, Ruriko Yoshida:
  On the enumeration of certain weighted graphs. 1481-1496
• 
  Changping Wang:
  The signed star domination numbers of the Cartesian product graphs. 1497-1505

Communications

• 
  Ioan Tomescu:
  On the number of words containing the factor (aba)^k. 1506-1511

Volume 155, Number 12, June 2007

SAT 2001, the Fourth International Symposium on the Theory and Applications of Satisfiability Testing

• 
  Henry A. Kautz, Bart Selman:
  The state of SAT. 1514-1524
• 
  Alexis C. Kaporis, Lefteris M. Kirousis, Yannis C. Stamatiou, Malvina Vamvakari, Michele Zito:
  The unsatisfiability threshold revisited. 1525-1538
• 
  Ilya Shlyakhter:
  Generating effective symmetry-breaking predicates for search problems. 1539-1548
• 
  Eugene Goldberg, Yakov Novikov:
  BerkMin: A fast and robust Sat-solver. 1549-1561
• 
  Brian C. Williams, Robert J. Ragno:
  Conflict-directed A^* and its role in model-based embedded systems. 1562-1595
• 
  Kazuo Iwama, Suguru Tamaki:
  Exploiting partial knowledge of satisfying assignments. 1596-1603
•