Discrete Applied Mathematics, Volume 156

Volume 156, Number 1, January 2008

Communications

• 
  S. Amghibech:
  On the discrete version of Picone's identity. 1-10
• 
  Jean-Luc Marichal, Pierre Mathonet:
  Approximations of Lovász extensions and their induced interaction index. 11-24
• 
  Sung-Pil Hong, Levent Tunçel:
  Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra. 25-41
• 
  Pankaj K. Agarwal, Ferran Hurtado, Godfried T. Toussaint, Joan Trias:
  On polyhedra induced by point sets in space. 42-54
• 
  Hsin-Hung Chou, Ming-Tat Ko, Chin-Wen Ho, Gen-Huey Chen:
  Node-searching problem on block graphs. 55-75

Notes

• 
  Derek H. Smith, Stephanie Perkins:
  Cyclically permutable representations of cyclic codes. 76-81
• 
  John Holliday, Peter D. Johnson Jr.:
  The Shields-Harary numbers of K_{m, n} for continuous concave cost functions vanishing at 1. 82-87
• 
  Ruijuan Li, Shengjia Li, Jinfeng Feng:
  The number of vertices whose out-arcs are pancyclic in a 2-strong tournament. 88-92
• 
  Vladimir Pozdnyakov:
  A note on occurrence of gapped patterns in i.i.d. sequences. 93-102
• 
  Hisayasu Kurata:
  Linear relations for p-harmonic functions. 103-109
• 
  József Balogh, Clifford D. Smyth:
  On the variance of Shannon products of graphs. 110-118
• 
  Toufik Mansour:
  Longest alternating subsequences of k-ary words. 119-124
• 
  Alexandru Ioan Tomescu:
  Unicyclic and bicyclic graphs having minimum degree distance. 125-130
• 
  Wai Hong Chan, Peter Che Bor Lam, Wai Chee Shiu:
  Cyclic bandwidth with an edge added. 131-137
• 
  Roland Grappe, Zoltán Szigeti:
  Covering symmetric semi-monotone functions. 138-144

Volume 156, Number 2, January 2008

Computational Methods for Graph Coloring and it's Generalizations

• 
  David S. Johnson, Anuj Mehrotra, Michael A. Trick:
  Special issue on computational methods for graph coloring and its generalizations. 145-146
• 
  Steven D. Prestwich:
  Generalised graph colouring by a hybrid of local search and constraint programming. 148-158
• 
  Isabel Méndez-Díaz, Paula Zabala:
  A cutting plane algorithm for graph coloring. 159-179
• 
  Igor Dukanovic, Franz Rendl:
  A semidefinite programming-based heuristic for graph coloring. 180-189
• 
  Thang Nguyen Bui, ThanhVu H. Nguyen, Chirag M. Patel, Kim-Anh T. Phan:
  An ant-based algorithm for coloring graphs. 190-200
• 
  Massimiliano Caramia, Paolo Dell'Olmo:
  Coloring graphs by iterated local search traversing feasible and infeasible solutions. 201-217
• 
  Kazunori Mizuno, Seiichi Nishihara:
  Constructive generation of very hard 3-colorability instances. 218-229
• 
  Allen Van Gelder:
  Another look at graph coloring via propositional satisfiability. 230-243
• 
  Christian Desrosiers, Philippe Galinier, Alain Hertz:
  Efficient algorithms for finding critical subgraphs. 244-266
• 
  Philippe Galinier, Alain Hertz, Nicolas Zufferey:
  An adaptive memory algorithm for the k-coloring problem. 267-279
• 
  Shahadat Hossain, Trond Steihaug:
  Graph coloring in the estimation of sparse derivative matrices: Instances and applications. 280-288

Volume 156, Number 3, February 2008

Combinatorial Optimization 2004, CO2004

• 
  Alistair R. Clark, Richard W. Eglese, Adam N. Letchford, Michael B. Wright:
  Preface. 289-290
• 
  Miroslav Chlebík, Janka Chlebíková:
  Crown reductions for the Minimum Weighted Vertex Cover problem. 292-312
• 
  Kathryn A. Dowsland, Jonathan M. Thompson:
  An improved ant colony optimisation heuristic for graph colouring. 313-324
• 
  Le Thi Hoai An, Pham Dinh Tao:
  A continuous approach for the concave cost supply problem via DC programming and DCA. 325-338
• 
  Carlo Mannino, Fabrizio Rossi, Antonio Sassano, Stefano Smriglio:
  Time offset optimization in digital broadcasting. 339-351
• 
  Cristóbal Miralles, José Pedro García-Sabater, Carlos Andrés, Manuel Cardós:
  Branch and bound procedures for solving the Assembly Line Worker Assignment and Balancing Problem: Application to Sheltered Work centres for Disabled. 352-367
• 
  Gerhard Reinelt, Dirk Oliver Theis:
  On the general routing polytope. 368-384
• 
  Gerhard Reinelt, Dirk Oliver Theis, Klaus Michael Wenger:
  Computing finest mincut partitions of a graph and application to routing problems. 385-396
• 
  Gerhard J. Woeginger:
  Open problems around exact algorithms. 397-405

Volume 156, Number 4, February 2008

Third Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics & Algorithm

• 
  Irith Ben-Arroyo Hartman, Seffi Naor, Michal Penn, Uriel G. Rothblum:
  The Third Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics, and Algorithms. 407-408
• 
  Irith Ben-Arroyo Hartman, Seffi Naor, Michal Penn, Uriel G. Rothblum:
  Editorial. 410-411
• 
  Michal Penn, Tal Raviv:
  A polynomial time algorithm for solving a quality control station configuration problem. 412-419
• 
  Aviezri S. Fraenkel:
  Games played by Boole and Galois. 420-427
• 
  Uriel G. Rothblum, Yoav Tangir:
  The partition bargaining problem. 428-443
• 
  Ephraim Korach, Michal Stern:
  The complete optimal stars-clustering-tree problem. 444-450
• 
  Martin Charles Golumbic, Marina Lipshteyn, Michal Stern:
  The k-edge intersection graphs of paths in a tree. 451-461
• 
  Ephraim Korach, Uri N. Peled, Udi Rotics:
  Equistable distance-hereditary graphs. 462-477
• 
  Vadim E. Levit, Eugen Mandrescu:
  On the roots of independence polynomials of almost all very well-covered graphs. 478-491
• 
  Yulia Kempner, Ilya B. Muchnik:
  Quasi-concave functions on meet-semilattices. 492-499
• 
  Vladimir R. Rosenfeld:
  The circuit polynomial of the restricted rooted product G(Gamma) of graphs with a bipartite core G. 500-510
• 
  Eldar Fischer, Johann A. Makowsky, Elena V. Ravve:
  Counting truth assignments of formulas of bounded tree-width or clique-width. 511-529
• 
  Robert H. Sloan, Balázs Szörényi, György Turán:
  Projective DNF formulae and their revision. 530-544

Volume 156, Number 5, March 2008

• 
  John Ellis, Robert Warren:
  Lower bounds on the pathwidth of some grid-like graphs. 545-555
• 
  Gerd Finke, Vincent Jost, Maurice Queyranne, András Sebö:
  Batch processing with interval graph compatibilities between tasks. 556-568
• 
  Christian Liebchen, Gregor Wünsch:
  The zoo of tree spanner problems. 569-587
• 
  S. Nishimura, T. Hiramatsu:
  A generalization of the Lee distance and error correcting codes. 588-595
• 
  Martin Gavalec, Ján Plávka:
  Structure of the eigenspace of a Monge matrix in max-plus algebra. 596-606
• 
  Ryan Pepper:
  An upper bound on the independence number of benzenoid systems. 607-619
• 
  Edmund K. Burke, Moshe Dror, James B. Orlin:
  Scheduling malleable tasks with interdependent processing rates: Comments and observations. 620-626
• 
  Donatella Merlini:
  Proper generating trees and their internal path length. 627-646
• 
  Yuqin Zhang:
  P₃-equicoverable graphs - Research on H-equicoverable graphs. 647-661
• 
  Irena Rusu:
  Maximum weight edge-constrained matchings. 662-672
• 
  Viera Borbel'ová, Katarína Cechlárová:
  On the stable b-matching problem in multigraphs. 673-684
• 
  Jean-Luc Marichal:
  Weighted lattice polynomials of independent random variables. 685-694
• 
  Ronald D. Dutton, Robert Lee, Robert C. Brigham:
  Bounds on a graph's security number. 695-704
• 
  Pinar Heggernes, Federico Mancini, Charis Papadopoulos:
  Minimal comparability completions of arbitrary graphs. 705-718
• 
  Srikrishnan Divakaran, Michael E. Saks:
  Approximation algorithms for problems in scheduling with set-ups. 719-729
• 
  Kah Loon Ng, P. Raff:
  A generalization of the firefighter problem on Z×Z. 730-745
• 
  David Eisenstat, Jennifer Feder, Greg Francos, Gary Gordon, Amanda Redlich:
  Expected rank and randomness in rooted graphs. 746-756
• 
  Xi-Ying Yuan, Jia-Yu Shao, Li Zhang:
  The six classes of trees with the largest algebraic connectivity. 757-769
• 
  Eva Yu-Ping Deng, Toufik Mansour:
  Three Hoppy path problems and ternary paths. 770-779
• 
  R. Julian R. Abel, Frank E. Bennett:
  Super-simple Steiner pentagon systems. 780-793
• 
  Frédéric Gardi:
  Mutual exclusion scheduling with interval graphs or related classes. Part II. 794-812
• 
  Pavel Chebotarev:
  Spanning forests and the golden ratio. 813-821

Volume 156, Number 6, March 2008

Discrete Mathematics and Data Mining II - DM & DM II

• 
  Martin Anthony, Endre Boros, Alexander Kogan:
  Preface. 823
• 
  Nicolas Peltier:
  Extended resolution simulates binary decision diagrams. 825-837
• 
  Boaz Golany, Frank K. Hwang, Uriel G. Rothblum:
  Sphere-separable partitions of multi-parameter elements. 838-845
• 
  Tibérius O. Bonates, Peter L. Hammer, Alexander Kogan:
  Maximum patterns in datasets. 846-861
• 
  János Demetrovics, Gyula O. H. Katona, Dezsö Miklós:
  Functional dependencies distorted by errors. 862-869
• 
  Gabriela Alexe, Sorin Alexe, Peter L. Hammer, Alexander Kogan:
  Comprehensive vs. comprehensible classifiers in logical analysis of data. 870-882
• 
  Martin Anthony:
  Aspects of discrete mathematics and probability in the theory of machine learning. 883-902
• 
  Joel Ratsaby:
  On the complexity of constrained VC-classes. 903-910
• 
  Pablo Cordero, Ángel Mora, Inman P. de Guzmán, Manuel Enciso:
  Non-deterministic ideal operators: An adequate tool for formalization in Data Bases. 911-923
• 
  Petko Valtchev, Rokia Missaoui, Robert Godin:
  A framework for incremental generation of closed itemsets. 924-949
• 
  Emilio Carrizosa, Belen Martin-Barragan, Dolores Romero Morales:
  Multi-group support vector machines with measurement costs: A biobjective approach. 950-966
• 
  Eric SanJuan:
  Heyting algebras with Boolean operators for rough sets and information retrieval applications. 967-983

Volume 156, Number 7, April 2008

GRACO 2005 - 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics

• 
  Paulo Feofiloff, Celina M. H. de Figueiredo, Yoshiko Wakabayashi:
  Preface. 985
• 
  Pierre Hansen, Dragan Stevanovic:
  On bags and bugs. 986-997
• 
  Arnaud Pêcher, Annegret Wagler:
  On classes of minimal circular-imperfect graphs. 998-1010
• 
  Zoltán Szigeti:
  Edge-splittings preserving local edge-connectivity of graphs. 1011-1018
• 
  Manoel Lemos, T. R. B. Melo:
  Non-separating cocircuits in matroids. 1019-1024
• 
  Carlos Eduardo Rodrigues Alves, E. N. Cáceres, Siang Wun Song:
  An all-substrings common subsequence algorithm. 1025-1035
• 
  Alois Panholzer:
  A distributional study of the path edge-covering numbers for random trees. 1036-1052
• 
  Mitre Costa Dourado, Fábio Protti, Jayme Luiz Szwarcfiter:
  On the strong p-Helly property. 1053-1057
• 
  Flavia Bonomo, Maria Chudnovsky, Guillermo Durán:
  Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs. 1058-1082
• 
  E. C. Xavier, Flávio Keidi Miyazawa:
  A one-dimensional bin packing problem with shelf divisions. 1083-1096
• 
  Manoel B. Campêlo, Victor A. Campos, Ricardo C. Corrêa:
  On the asymmetric representatives formulation for the vertex coloring problem. 1097-1111
• 
  Conor Meagher, Bruce A. Reed:
  Fractionally total colouring G_{n, p}. 1112-1124
• 
  Martín Matamala, José Zamora:
  A new family of expansive graphs. 1125-1131
• 
  José Cáceres, M. Carmen Hernando, Mercè Mora, Ignacio M. Pelayo, María Luz Puertas, Carlos Seara:
  Geodeticity of the contour of chordal graphs. 1132-1142
• 
  Jirí Fiala, Jan Kratochvíl, Attila Pór:
  On the computational complexity of partial covers of Theta graphs. 1143-1149
• 
  Bruce A. Reed:
  Skew partitions in perfect graphs. 1150-1156
• 
  Francisco Larrión, Miguel A. Pizaña:
  On hereditary clique-Helly self-clique graphs. 1157-1167
• 
  Louigi Addario-Berry, Ketan Dalal, Bruce A. Reed:
  Degree constrained subgraphs. 1168-1174
• 
  Samuel Fiorini, Nadia Hardy, Bruce A. Reed, Adrian Vetta:
  Planar graph bipartization in linear time. 1175-1180

Volume 156, Number 8, April 2008

Ordinal and Symbolic Data Analysis - OSDA 2003, Ordinal and Symbolic Data Analysis Conference

• 
  Olivier Hudry, Melvin F. Janowitz, Sergei Ovchinnikov:
  Preface. 1181
• 
  Jean-Claude Falmagne, Yung-Fong Hsu, Fabio Leite, Michel Regenwetter:
  Stochastic applications of media theory: Random walks on weak orders or partial orders. 1183-1196
• 
  Sergei Ovchinnikov:
  Media theory: Representations and examples. 1197-1219
• 
  Patrice Bertrand:
  Systems of sets such that each set properly intersects at most one other set - Application to cluster analysis. 1220-1236
• 
  Jean-Pierre Barthélemy, François Brucker:
  Binary clustering. 1237-1250
• 
  Frédéric Guyon, Alain Guénoche:
  Comparing bacterial genomes from linear orders of patterns. 1251-1262
• 
  Bernard Fichet:
  The 22 minimal dichotomy decompositions of the K₅-distance. 1263-1270
• 
  Edwin Diday:
  Spatial classification. 1271-1294
• 
  Mohammed Benayade, Jean Diatta:
  Cluster structures and collections of Galois closed entity subsets. 1295-1307
• 
  David Eppstein, Jean-Claude Falmagne:
  Algorithms for media. 1308-1320
• 
  Robert C. Powers, Jeremy M. White:
  Wilson's theorem for consensus functions on hierarchies. 1321-1329
• 
  Irène Charon, Olivier Hudry:
  Optimal clustering of multipartite graphs. 1330-1341

Volume 156, Number 9, May 2008

General Theory of Information Transfer and Combinatorics

• 
  Rudolf Ahlswede:
  Preface. 1343-1344
• 
  Harout K. Aydinian:
  Levon H. Khachatrian: 1954-2002. 1346-1347

Section 1

• 
  Rudolf Ahlswede:
  General theory of information transfer: Updated. 1348-1388
• 
  Alberto Apostolico, Raffaele Giancarlo:
  Periodicity and repetitions in parameterized strings. 1389-1398
• 
  Vladimir I. Levenshtein, Elena V. Konstantinova, Eugene Konstantinov, Sergey G. Molodtsov:
  Reconstruction of a graph from 2-vicinities of its vertices. 1399-1406

Section 2

• 
  Sándor Györi:
  Coding for a multiple access OR channel: A survey. 1407-1430
• 
  Rudolf Ahlswede:
  Ratewise-optimal non-sequential search strategies under constraints on the tests. 1431-1443
• 
  Rudolf Ahlswede, Ferdinando Cicalese, Christian Deppe:
  Searching with lies under error cost constraints. 1444-1460
• 
  Rudolf Ahlswede, Bernhard Balkenhol, Christian Deppe, Haik Mashurian, T. Partner:
  T-shift synchronization codes. 1461-1468
• 
  Rudolf Ahlswede, Vladimir M. Blinovsky:
  Multiple packing in sum-type metric spaces. 1469-1477
• 
  Rudolf Ahlswede, Julien Cassaigne, András Sárközy:
  On the correlation of binary sequences. 1478-1487

Section 3

• 
  Faina I. Solov'eva:
  On perfect binary codes. 1488-1498
• 
  Rossitza Dodunekova, Stefan M. Dodunekov, Evgeniya P. Nikolova:
  A survey on proper codes. 1499-1509
• 
  Christian Bey:
  The edge-diametric theorem in Hamming spaces. 1510-1517
• 
  Mathieu Dutour Sikiric, Michel Deza, Mikhail Shtogrin:
  Filling of a given boundary by p-gons and related problems. 1518-1535
• 
  Zoltán Füredi, Miklós Ruszinkó:
  Large convex cones in hypercubes. 1536-1541
•