Discrete Applied Mathematics, Volume 159

Volume 159, Number 1, January 2011

Contributions

• 
  Irénée Briquel, Pascal Koiran, Klaus Meer:
  On the expressive power of CNF formulas of bounded tree- and clique-width. 1-14
• 
  Brian C. Dean, Sandra Mitchell Hedetniemi, Stephen T. Hedetniemi, Jason Lewis, Alice A. McRae:
  Matchability and k-maximal matchings. 15-22
• 
  Flavio Guiñez, Martín Matamala, Stéphan Thomassé:
  Realizing disjoint degree sequences of span at most two: A tractable discrete tomography problem. 23-30
• 
  Arne Bang Huseby:
  Oriented matroid systems. 31-45
• 
  Moo Young Sohn, Dongseok Kim, Young Soo Kwon, Jaeun Lee:
  On the existence problem of the total domination vertex critical graphs. 46-52
• 
  Daniel Cosmin Porumbel, Jin-Kao Hao, Pascale Kuntz:
  An efficient algorithm for computing the distance between close partitions. 53-59
• 
  Clara Inés Betancur Velasquez, Flavia Bonomo, Ivo Koch:
  On the b-coloring of P₄-tidy graphs. 60-68
• 
  Rundan Xing, Bo Zhou:
  On the revised Szeged index. 69-78

Notes

• 
  Jochen Harant, Dieter Rautenbach:
  Independence in connected graphs. 79-86
• 
  Nicolas Roussel:
  Total choosability of planar graphs with maximum degree 4. 87-89

Volume 159, Numbers 2-3, January 2011

Contributions

• 
  Camino Balbuena, Pedro García-Vázquez, Luis Pedro Montejano:
  Superconnectivity of graphs with odd girth g and even girth h. 91-99
• 
  Kim A. S. Factor, Sarah K. Merz:
  The (1, 2)-step competition graph of a tournament. 100-103
• 
  Michael A. Henning, Nader Jafari Rad:
  Total domination dot-critical graphs. 104-111
• 
  Alexander K. Kelmans:
  Packing 3-vertex paths in claw-free graphs and related topics. 112-127
• 
  Richard Krueger, Geneviève Simonet, Anne Berry:
  A General Label Search to investigate classical graph search algorithms. 128-142
• 
  Anders Sune Pedersen, Dieter Rautenbach, Friedrich Regen:
  Lower bounds on the independence number of certain graphs of odd girth at least seven. 143-151

Notes

• 
  Meysam Alishahi:
  On the dynamic coloring of graphs. 152-156
• 
  Jianfeng Hou, Bin Liu, Guizhen Liu, Jianliang Wu:
  Total coloring of planar graphs without 6-cycles. 157-163

Volume 159, Number 4, February 2011

Contributions

• 
  Raquel S. F. Bravo, Sulamita Klein, Loana Tito Nogueira, Fábio Protti:
  Characterization and recognition of P₄-sparse graphs partitionable into k independent sets and l cliques. 165-173
• 
  Csilla Bujtás, E. Sampathkumar, Zsolt Tuza, L. Pushpalatha, R. C. Vasundhara:
  Improper C-colorings of graphs. 174-186
• 
  Giulia Galbiati, Romeo Rizzi, Edoardo Amaldi:
  On the approximability of the minimum strictly fundamental cycle basis problem. 187-200
• 
  Enkelejd Hashorva:
  Asymptotics of the convex hull of spherically symmetric samples. 201-211
• 
  Shangwei Lin, Shiying Wang, Chunfang Li:
  Panconnectivity and edge-pancyclicity of k-ary n-cubes with faulty elements. 212-223
• 
  José M. Sigarreta Almira, Ismael González Yero, Sergio Bermudo, Juan Alberto Rodríguez-Velázquez:
  Partitioning a graph into offensive k-alliances. 224-231
• 
  Yingqian Wang, Qian Wu, Liang Shen:
  Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable. 232-239

Notes

• 
  Xiang-Feng Pan, Ning-Ning Lv:
  Sharp bounds of the zeroth-order general Randic index of bicyclic graphs with given pendent vertices. 240-245
• 
  Zdenek Ryjácek, Gerhard J. Woeginger, Liming Xiong:
  Hamiltonian index is NP-complete. 246-250
• 
  Karin Thörnblad, Michael Patriksson:
  A note on the complexity of flow-shop scheduling with deteriorating jobs. 251-253

Volume 159, Number 5, March 2011

Special Section: Boolean and Pseudo-Boolean Functions

• 
  Frank Markham Brown:
  On the suppression of variables in Boolean equations. 255-258
• 
  Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan:
  Learning random monotone DNF. 259-271

Contributions

• 
  Philippe Baptiste, Jacques Carlier, Alexander V. Kononov, Maurice Queyranne, Sergey Sevastyanov, Maxim Sviridenko:
  Properties of optimal schedules in preemptive shop scheduling. 272-280
• 
  sarah-marie belcastro, Michael Young:
  1-factor covers of regular graphs. 281-287
• 
  Flavia Bonomo, Guillermo Durán, Javier Marenco, Mario Valencia-Pabon:
  Minimum sum set coloring of trees and line graphs of trees. 288-294
• 
  Pavel Chebotarev:
  A class of graph-geodetic distances generalizing the shortest-path and the resistance distances. 295-302
• 
  Christine T. Cheng, Ichiro Suzuki:
  Weak sense of direction labelings and graph embeddings. 303-310
• 
  Vladimir Gurvich:
  On exact blockers and anti-blockers, Δ-conjecture, and related problems. 311-321
• 
  Hovhannes A. Harutyunyan, Pavol Hell, Arthur L. Liestman:
  Messy broadcasting - Decentralized broadcast schemes with limited knowledge. 322-327
• 
  Jonelle Hook, Garth Isaak:
  Star-critical Ramsey numbers. 328-334
• 
  Ville Junnila, Tero Laihonen:
  Identification in Z2 using Euclidean balls. 335-343
• 
  Martin Knor, Guangjun Xu, Sanming Zhou:
  A study of 3-arc graphs. 344-353
• 
  Vadim E. Levit, David Tankus:
  Weighted well-covered graphs without C₄, C₅, C₆, C₇. 354-359
• 
  Paul D. Manuel:
  Minimum average congestion of enhanced and augmented hypercubes into complete binary trees. 360-366
• 
  Dara Moazzami:
  Tenacity of a graph with maximum connectivity. 367-380
• 
  Ján Plávka, Peter Szabó:
  On the λ-robustness of matrices over fuzzy algebra. 381-388
• 
  Dieter Rautenbach, Vinícius Fernandes dos Santos, Philipp Matthias Schäfer, Jayme Luiz Szwarcfiter:
  Characterization and representation problems for intersection betweennesses. 389-395

Note

• 
  Silvia M. Bianchi, Mariana S. Escalante, Graciela L. Nasini:
  On the behavior of the N₊-operator under blocker duality. 396-399

Volume 159, Number 6, March 2011

Special Section: Computational Molecular Biology

• 
  Julio Aracena, Eric Fanchon, Marco Montalva, Mathilde Noual:
  Combinatorics on update digraphs in Boolean networks. 401-409
• 
  Ruth Charney, Jacques Cohen, Aurélien Rizk:
  Efficient synthesis of a class of Boolean programs from I-O data: Application to genetic networks. 410-419

Contributions

• 
  Oded Berman, Dmitry Krass:
  On n-facility median problem with facilities subject to failure facing uniform demand. 420-432
• 
  Yago Diez, Joan Antoni Sellarès:
  Noisy colored point set matching. 433-449
• 
  Felix Distel, Baris Sertkaya:
  On the complexity of enumerating pseudo-intents. 450-466
• 
  Hong-Jian Lai, Yanting Liang:
  Supereulerian graphs in the graph family C₂(6, k). 467-477
• 
  Kun Meng, Chuang Lin, Wen An Liu, Yang Yang:
  Q-ary Rényi-Ulam pathological liar game with one lie. 478-483
• 
  Suk Jai Seo, Peter J. Slater:
  Open neighborhood locating-dominating in trees. 484-489

Note

• 
  Yiu Yu Ho, Ronald D. Dutton:
  Global secure sets of grid-like graphs. 490-496

Volume 159, Number 7, April 2011

• 
  Marina Lipshteyn, Ross M. McConnell, Haim Kaplan, Vadim E. Levit:
  Foreword. 497
• 
  Yuichi Asahiro, Eiji Miyano, Hirotaka Ono:
  Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree. 498-508
• 
  Andreas Brandstädt, Raffaele Mosca:
  On distance-3 matchings and induced matchings. 509-520
• 
  Domingos Moreira Cardoso, Nicholas Korpelainen, Vadim V. Lozin:
  On the complexity of the dominating induced matching problem in hereditary classes of graphs. 521-531
• 
  Márcia R. Cerioli, Fabiano de S. Oliveira, Jayme Luiz Szwarcfiter:
  On counting interval lengths of interval graphs. 532-543
• 
  Mirela Ben-Chen, Steven J. Gortler, Craig Gotsman, Camille Wormser:
  Distributed computation of virtual coordinates for greedy routing in sensor networks. 544-560
• 
  Celina M. H. de Figueiredo, Frédéric Maffray, Cláudia Villela Maciel:
  Transitive orientations in bull-reducible Berge graphs. 561-573
• 
  Arnaud Durand, Michel Habib:
  Complexity issues for the sandwich homogeneous set problem. 574-580
• 
  Elaine M. Eschen, Chính T. Hoàng, Jeremy P. Spinrad, R. Sritharan:
  On graphs without a C₄ or a diamond. 581-587
• 
  Danny Hermelin, Dror Rawitz:
  Optimization problems in multiple subtree graphs. 588-594
• 
  Robert E. Jamison:
  Orientable edge colorings of graphs. 595-604
• 
  Hal A. Kierstead, Karin Rebecca Saoub:
  First-Fit coloring of bounded tolerance graphs. 605-611
• 
  Jonathan Lenchner:
  On the affine Sylvester problem. 612-620
• 
  Min Chih Lin, Dieter Rautenbach, Francisco J. Soulignac, Jayme Luiz Szwarcfiter:
  Powers of cycles, powers of paths, and distance graphs. 621-627
• 
  Azaria Paz:
  A theory of decomposition into prime factors of layered interconnection networks. 628-646
• 
  Alan Shuchat, Randy Shull, Ann N. Trenk:
  Fractional weak discrepancy and split semiorders. 647-660
• 
  Rafael B. Teixeira, Simone Dantas, Celina M. H. de Figueiredo:
  The external constraint 4 nonempty part sandwich problem. 661-673

Volume 159, Number 8, April 2011

Special Section: Game Theory

• 
  Carlos Pereira dos Santos:
  Embedding processes in combinatorial game theory. 675-682
• 
  John Y. Kim:
  The incidence game chromatic number of paths and subgraphs of wheels. 683-694

Contributions

• 
  David Adjiashvili, Rico Zenklusen:
  An s-t connection problem with adaptability. 695-705
• 
  Behrooz Alizadeh, Rainer E. Burkard:
  Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees. 706-716
• 
  Jonathan Backer:
  Separator orders in interval, cocomparability, and AT-free graphs. 717-726
• 
  Bing Bai, Hongliang Lu, Qinglin Yu:
  Generalization of matching extensions in graphs (III). 727-732
• 
  Francine Blanchet-Sadri, John Lensmire:
  On minimal Sturmian partial words. 733-745
• 
  R. Chandrasekaran, Milind Dawande, Mehmet Baysan:
  On a labeling problem in graphs. 746-759
• 
  Gerard Jennhwa Chang, Jianfeng Hou, Nicolas Roussel:
  Local condition for planar graphs of maximum degree 7 to be 8-totally colorable. 760-768
• 
  Xue-Gang Chen, Moo Young Sohn:
  Bounds on the locating-total domination number of a tree. 769-773
• 
  Jun-Lin Guo, Tao-Ming Wang, Yue-Li Wang:
  Unique intersectability of diamond-free graphs. 774-778
• 
  Aleksandar Ilic, Dragan Stevanovic, Lihua Feng, Guihai Yu, Peter Dankelmann:
  Degree distance of unicyclic and bicyclic graphs. 779-788
• 
  Mihyun Kang, Oleg Pikhurko, Alexander Ravsky, Mathias Schacht, Oleg Verbitsky:
  Untangling planar graphs from a specified vertex position - Hard cases. 789-799
• 
  Qiuli Li, Saihua Liu, Heping Zhang:
  2-extendability and k-resonance of non-bipartite Klein-bottle polyhexes. 800-811
• 
  Ali Haydar Özer, Can C. Özturan:
  A direct barter model for course add/drop process. 812-825
• 
  Valery T. Stefanov, Stéphane Robin, Sophie Schbath:
  Occurrence of structured motifs in random sequences: Arbitrary number of boxes. 826-831
• 
  Lutz Volkmann:
  Upper bounds on the signed total domatic number of graphs. 832-837
• 
  Jinjiang Yuan, C. T. Ng, T. C. Edwin Cheng:
  Best semi-online algorithms for unbounded parallel batch scheduling. 838-847

Notes

• 
  R. Julian R. Abel, Ian Anderson, Norman J. Finizio:
  Necessary conditions for the existence of two classes of ZCPS-Wh(v). 848-851
• 
  Vesna Andova, Saso Bogoev, Darko Dimitrov, Marcin Pilipczuk, Riste Skrekovski:
  On the Zagreb index inequality of graphs with prescribed vertex degrees. 852-858
• 
  Adrian Dumitrescu, Minghui Jiang:
  Constrained k-center and movement to independence. 859-865
• 
  Mehdi Eliasi, Ali Iranmanesh:
  The hyper-Wiener index of the generalized hierarchical product of graphs. 866-871
• 
  Hermann Gruber:
  Bounding the feedback vertex number of digraphs in terms of vertex degrees. 872-875
• 
  Jianfeng Hou, Guizhen Liu, Guanghui Wang:
  Improved bounds for acyclic chromatic index of planar graphs. 876-881

Volume 159, Number 9, June 2011

• 
  Géraldine Heilporn, Jean-François Cordeau, Gilbert Laporte:
  An integer L-shaped algorithm for the Dial-a-Ride Problem with stochastic customer delays. 883-895
• 
  Evangelos Kranakis, Danny Krizanc, Euripides Markou:
  Deterministic symmetric rendezvous with tokens in a synchronous torus. 896-923
• 
  Yuanliang Zhang, Olga I. Kostyukova, Kil To Chong:
  A new time-discretization for delay multiple-input nonlinear systems using the Taylor method and first order hold. 924-938

Note

• 
  Henry Martyn Mulder, Beth Novick:
  An axiomatization of the median procedure on the n-cube. 939-944

Volume 159, Number 10, June 2011

• 
  Peter Dankelmann:
  On the distance distribution of trees. 945-952
• 
  Nicole Eggemann, Steven D. Noble:
  The clustering coefficient of a scale-free random graph. 953-965
• 
  Jochen Harant:
  A lower bound on independence in terms of degrees. 966-970
• 
  Hongbo Hua, Shenggui Zhang:
  Graphs with given number of cut vertices and extremal Merrifield-Simmons index. 971-980
• 
  Raphaël M. Jungers, Vincent D. Blondel:
  Observable graphs. 981-989
• 
  Léonard Kwuida, Stefan E. Schmidt:
  Valuations and closure operators on finite lattices. 990-1001
• 
  Yingjie Lan, Songqing Chen:
  Some special minimum k-geodetically connected graphs. 1002-1012
• 
  Anders Sune Pedersen, Dieter Rautenbach:
  Recolouring-resistant colourings. 1013-1021
• 
  Yann Strozecki:
  Monadic second-order model-checking on decomposable matroids. 1022-1039
• 
  Munevver Mine Subasi, Ersoy Subasi, Martin Anthony, Peter L. Hammer:
  A new imputation method for incomplete binary data. 1040-1047

Notes

• 
  Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. Henning:
  An extremal problem for total domination stable graphs upon edge removal. 1048-1052
• 
  Stephanie A. Rickett, Teresa W. Haynes:
  Total domination dot-stable graphs. 1053-1057

Erratum

• 
  Hande Yaman:
  Erratum to: Polyhedral analysis for the two-item uncapacitated lot-sizing problem with one-way substitution [Discrete Appl. Math. 157 (2009) 3133-3151]. 1058

Volume 159, Number 11, July 2011

Special Section: Computational Molecular Biology

• 
  David Canright, Sugata Gangopadhyay, Subhamoy Maitra, Pantelimon Stanica:
  Laced Boolean functions and subset sum problems in finite fields. 1059-1069
• 
  Ferdinando Cicalese, Travis Gagie, Eduardo Sany Laber, Martin Milanic:
  Competitive Boolean function evaluation: Beyond monotonicity, and the symmetric case. 1070-1078
• 
  Javier Herranz:
  Any 2-asummable bipartite function is weighted threshold. 1079-1084
• 
  Adrien Richard:
  Local negative circuits and fixed points in non-expansive Boolean networks. 1085-1093

Contributions

• 
  David Coudert, Jean-Sébastien Sereni:
  Characterization of graphs and digraphs with small process numbers. 1094-1109
• 
  E. Ebrahimi Targhi, Nader Jafari Rad, Lutz Volkmann:
  Unique response Roman domination in graphs. 1110-1117
• 
  Michael R. Fellows, Henning Fernau:
  Facility location problems: A parameterized view. 1118-1130
• 
  George B. Mertzios, Derek G. Corneil:
  Vertex splitting and the recognition of trapezoid graphs. 1131-1147
• 
  Stefko Miklavic, Martin Milanic:
  Equistable graphs, general partition graphs, triangle graphs, and graph products. 1148-1159

Notes

• 
  Pranav Anand, Henry Escuadro, Ralucca Gera, Craig H. Martell:
  Triangular line graphs and word sense disambiguation. 1160-1165
• 
  Nicola Apollonio, Massimiliano Caramia:
  Recognizing Helly Edge-Path-Tree graphs and their clique graphs. 1166-1175
• 
  Maurizio Monge:
  On perfect hashing of numbers with sparse digit representation via multiplication by a constant. 1176-1179
• 
  Dieter Rautenbach:
  Average distance and domination number revisited. 1180-1182
• 
  Huiyu Sheng, Yingqian Wang:
  A structural theorem for planar graphs with some applications. 1183-1187

Volume 159, Number 12, July 2011

• 
  Bostjan Bresar, Frantisek Kardos, Ján Katrenic, Gabriel Semanisin:
  Minimum k-path vertex cover. 1189-1195
•