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
• 
  Alexandr V. Kostochka, Gexin Yu:
  Minimum degree conditions for H-linked graphs. 1542-1548
• 
  Gohar M. Kyureghyan:
  Minimal polynomials of the modified de Bruijn sequences. 1549-1553
• 
  Melsik K. Kyuregyan:
  Recursive constructions of N-polynomials over GF(2^s). 1554-1559
• 
  Ulrich Tamm:
  Size of downsets in the pushing order and a problem of Berlekamp. 1560-1566

Volume 156, Number 10, May 2008

• 
  Pantelimon Stanica, Subhamoy Maitra:
  Rotation symmetric Boolean functions - Count and cryptographic properties. 1567-1580
• 
  Guoli Ding, Robert F. Lax, Jianhua Chen, Peter P. Chen:
  Formulas for approximating pseudo-Boolean random variables. 1581-1597
• 
  Daya Ram Gaur, Ramesh Krishnamurti:
  Self-duality of bounded monotone boolean functions and related problems. 1598-1605
• 
  Uwe Bubeck, Hans Kleine Büning:
  Models and quantifier elimination for quantified Horn formulas. 1606-1622
• 
  Deborah S. Franzblau, George Xenakis:
  An algorithm for the difference between set covers. 1623-1632
• 
  Martin Charles Golumbic, Aviad Mintz, Udi Rotics:
  An improvement on the complexity of factoring read-once Boolean functions. 1633-1636

Regular Papers

• 
  Charles R. Johnson, Joshua A. Link:
  The extent to which triangular sub-patterns explain minimum rank. 1637-1651
• 
  Tínaz Ekim, Nadimpalli V. R. Mahadev, Dominique de Werra:
  Polar cographs. 1652-1660
• 
  Klavdija Kutnar, Dragan Marusic:
  On cyclic edge-connectivity of fullerenes. 1661-1669
• 
  Francesco Belardo, Enzo Maria Li Marzi, Slobodan K. Simic:
  Ordering graphs with index in the interval (2, sqrt(2+sqrt(5))). 1670-1682
• 
  Jean-Philippe Hamiez, Jin-Kao Hao:
  Using solution properties within an enumerative search to solve a sports league scheduling problem. 1683-1693
• 
  Yoshiko Ikebe, Akihisa Tamura:
  On the existence of sports schedules with multiple venues. 1694-1710
• 
  Andrej Taranenko, Aleksander Vesel:
  Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphs. 1711-1724
• 
  Anhua Lin, Rong Luo, Xiaoya Zha:
  A sharp lower bound of the Randic index of cacti with r pendants. 1725-1735
• 
  Robert Brijder, Hendrik Jan Hoogeboom, Michael Muskulus:
  Strategies of loop recombination in ciliates. 1736-1753
• 
  Hans van Maaren, Linda van Norden, M. J. H. Heule:
  Sums of squares based approximation algorithms for MAX-SAT. 1754-1779
• 
  M. H. Khalifeh, Hassan Yousefi-Azari, A. R. Ashrafi:
  Vertex and edge PI indices of Cartesian product graphs. 1780-1789
• 
  Xueliang Li, Chao Wang, Xiaoyan Zhang:
  The general sigma all-ones problem for trees. 1790-1801
• 
  Sun-Yuan Hsieh, Tzu-Hsiung Shen:
  Edge-bipancyclicity of a hypercube with faulty vertices and edges. 1802-1808
• 
  Shan Zhou, Heping Zhang, Ivan Gutman:
  Relations between Clar structures, Clar covers, and the sextet-rotation tree of a hexagonal system. 1809-1821
• 
  Boting Yang, Yi Cao:
  Digraph searching, directed vertex separation and directed pathwidth. 1822-1837
• 
  Li-Da Tong, Pei-Lan Yen, Alastair Farrugia:
  The convexity spectra of graphs. 1838-1845
• 
  D. Jacob Wildstrom:
  Cost thresholds for dynamic resource location. 1846-1855
• 
  Yuejian Peng, Cheng Zhao:
  Generating non-jumping numbers recursively. 1856-1864
• 
  Frank Gurski:
  Graph parameters measuring neighbourhoods in graphs - Bounds and applications. 1865-1874
• 
  Hadrien Mélot:
  Facet defining inequalities among graph invariants: The system GraPHedron. 1875-1891
• 
  Wenping Zheng, Xiaohui Lin, Yuansheng Yang, Chengrui Deng:
  On the crossing numbers of K_msquare C_n and K_{m, l}square P_n. 1892-1907
• 
  Cédric Bentz:
  On the complexity of the multicut problem in bounded tree-width graphs and digraphs. 1908-1917
• 
  Geir Agnarsson, Ágúst S. Egilsson, Magnús M. Halldórsson:
  Vertex coloring acyclic digraphs and their corresponding hypergraphs. 1918-1928
• 
  Jürgen Rietz, Stephan Dempe:
  Large gaps in one-dimensional cutting stock problems. 1929-1935
• 
  Dieter Kratsch, Haiko Müller, Ioan Todinca:
  Feedback vertex set on AT-free graphs. 1936-1947

Notes

• 
  Zhao Zhang, Jixiang Meng:
  Super-connected edge transitive graphs. 1948-1953

Volume 156, Number 11, June 2008

In Memory of Leonid Khachiyan (1952 - 2005 )

• 
  Vladimir Gurvich:
  Recalling Leo. 1957-1960
• 
  Vasek Chvátal:
  Remembering Leo Khachiyan. 1961-1962
• 
  Rainer E. Burkard, Elisabeth Gassner, Johannes Hatzl:
  Reverse 2-median problem on trees. 1963-1976
• 
  Adi Ben-Israel, Yuri Levin:
  The Newton Bracketing method for the minimization of convex functions subject to affine constraints. 1977-1987
• 
  Nikolai S. Kukushkin:
  On the existence of maximal elements: An impossibility theorem. 1988-1993
• 
  Sergei O. Kuznetsov, Sergei A. Obiedkov:
  Some decision and counting problems of the Duquenne-Guigues basis of implications. 1994-2003
• 
  Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige:
  Minimizing a monotone concave function with laminar covering constraints. 2004-2019
• 
  Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich:
  Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions. 2020-2034
• 
  Thomas Eiter, Kazuhisa Makino, Georg Gottlob:
  Computational aspects of monotone dualization: A brief survey. 2035-2049
• 
  Toshihide Ibaraki, Shinji Imahori, Koji Nonobe, Kensuke Sobue, Takeaki Uno, Mutsunori Yagiura:
  An iterated local search algorithm for the vehicle routing problem with convex time penalty functions. 2050-2069
• 
  Sergey P. Tarasov, Mikhail N. Vyalyi:
  Semidefinite programming and arithmetic circuit evaluation. 2070-2078
• 
  Yurii E. Nesterov:
  Parabolic target space and primal-dual interior-point methods. 2079-2100
• 
  Xiaomin Chen, Vasek Chvátal:
  Problems related to a de Bruijn-Erdös theorem. 2101-2108
• 
  Khaled M. Elbassioni:
  On the complexity of monotone dualization and generating minimal hypergraph transversals. 2109-2123
• 
  Bernd Gärtner, Jirí Matousek, Leo Rüst, Petr Skovron:
  Violator spaces: Structure and algorithms. 2124-2141
• 
  Warren P. Adams, Paul T. Hadavas:
  A network approach for specially structured linear programs arising in 0-1 quadratic optimization. 2142-2165
• 
  Antoine Deza, Sui Huang, Tamon Stephen, Tamás Terlaky:
  The colourful feasibility problem. 2166-2177
• 
  Tamás Terlaky, Anthony Vannelli, Hu Zhang:
  On routing in VLSI design and communication networks. 2178-2194
• 
  Sergei G. Vorobyov:
  Cyclic games and linear programming. 2195-2231
• 
  Endre Boros, Vladimir Gurvich:
  Scientific contributions of Leo Khachiyan (a short overview). 2232-2240

Volume 156, Number 12, June 2008

• 
  Weifan Wang, Leizhen Cai:
  Labelling planar graphs without 4-cycles with a condition on distance two. 2241-2249
• 
  Geoffrey Exoo, Tero Laihonen, Sanna M. Ranto:
  New bounds on binary identifying codes. 2250-2263
• 
  Jung Hee Cheon, HongTae Kim:
  Analysis of Low Hamming Weight Products. 2264-2269
• 
  Márcia R. Cerioli, Luérbio Faria, Talita O. Ferreira, Carlos A. J. Martinhon, Fábio Protti, Bruce A. Reed:
  Partition into cliques for cubic graphs: Planar case, complexity and approximation. 2270-2278
• 
  Toufik Mansour, Yidong Sun:
  Bell polynomials and k-generalized Dyck paths. 2279-2292
• 
  Guizhen Liu, Lanju Zhang:
  Characterizations of maximum fractional (g, f)-factors of graphs. 2293-2299
• 
  Yinghua Duan, Haidong Wu, Qinglin Yu:
  On chromatic and flow polynomial unique graphs. 2300-2309
• 
  Pierre Fraigniaud, David Ilcinkas, Andrzej Pelc:
  Impact of memory size on graph exploration capability. 2310-2319
• 
  Niklas Eriksen:
  Expected number of breakpoints after t random reversals in genomes with duplicate genes. 2320-2335
• 
  Frank K. Hwang, J. S. Lee, Uriel G. Rothblum:
  Equivalence of permutation polytopes corresponding to strictly supermodular functions. 2336-2343
• 
  Benedek Nagy:
  Distance with generalized neighbourhood sequences in n D and infinity D. 2344-2351
• 
  Shigeto Nishimura:
  On a Riemann hypothesis analogue for selfdual weight enumerators of genus less than 3. 2352-2358
• 
  Jiehua Zhu, Xiezhang Li, Yangbo Ye, Ge Wang:
  Analysis on the strip-based projection model for discrete tomography. 2359-2367
• 
  Seok-Hee Hong, Hiroshi Nagamochi:
  Convex drawings of graphs with non-convex boundary constraints. 2368-2380
• 
  Partha Bhowmick, Bhargab B. Bhattacharya:
  Number-theoretic interpretation and construction of a digital circle. 2381-2399
• 
  Geng-sheng Zhang, Bo-li Li, Xiao-lei Sun, Feng-xia Li:
  A construction of d^z-disjunct matrices in a dual space of symplectic space. 2400-2406
• 
  Shoujun Xu, Heping Zhang:
  Hosoya polynomials under gated amalgamations. 2407-2419

Notes

• 
  Peter Dankelmann, Gert Sabidussi:
  Embedding graphs as isometric medians. 2420-2422
• 
  Sachin Gautam, Ashish Kumar Srivastava, Amitabha Tripathi:
  On multicolour noncomplete Ramsey graphs of star graphs. 2423-2428

Communications

• 
  Gregory Z. Gutin, Arash Rafiey, Anders Yeo:
  Minimum cost homomorphisms to semicomplete multipartite digraphs. 2429-2435

Volume 156, Number 13, July 2008

Fifth International Conference on Graphs and Optimization - GO V, 2006, Graphs and Optimization, 5th Conference

• 
  Dominique de Werra, Endre Boros, Jacques Carlier, Alain Hertz, Marino Widmer:
  Foreword. 2437-2438
• 
  Andrea Scozzari, Fabio Tardella:
  A clique algorithm for standard quadratic programming. 2439-2448
• 
  Bruno Simeone:
  A pseudo-Boolean consensus approach to nonlinear 0-1 optimization. 2449-2458
• 
  Jan Adem, Yves Crama, Willy Gochet, Frits C. R. Spieksma:
  Counting and enumerating aggregate classifiers. 2459-2468
• 
  Tínaz Ekim, Pavol Hell, Juraj Stacho, Dominique de Werra:
  Polarity of chordal graphs. 2469-2479
• 
  Nadia Brauner:
  Identical part production in cyclic robotic cells: Concepts, overview and open questions. 2480-2492
• 
  Dariusz Dereniowski:
  Edge ranking and searching in partial orders. 2493-2500
• 
  Yerim Chung, Marc Demange:
  The 0-1 inverse maximum stable set problem. 2501-2516
• 
  Vadim V. Lozin, Martin Milanic:
  On finding augmenting graphs. 2517-2529
• 
  Mustapha Aouchiche, Gunnar Brinkmann, Pierre Hansen:
  Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number. 2530-2542
• 
  Philippe Chrétienne:
  On single-machine scheduling without intermediate delays. 2543-2550
• 
  Alain Hertz, Matthieu Plumettaz, Nicolas Zufferey:
  Variable space search for graph coloring. 2551-2560
• 
  Peter Brucker, Thomas Kampmeyer:
  A general model for cyclic machine scheduling problems. 2561-2572
• 
  Jacek Blazewicz, Marta Kasprzak, Benjamin Leroy-Beaulieu, Dominique de Werra:
  Finding Hamiltonian circuits in quasi-adjoint graphs. 2573-2580

Volume 156, Number 14, July 2008

• 
  Tero Harju, Ion Petre, Vladimir Rogojin, Grzegorz Rozenberg:
  Patterns of simple gene assembly in ciliates. 2581-2597
• 
  Ji-Ming Guo:
  On the minimal energy ordering of trees with perfect matchings. 2598-2605
• 
  Predrag S. Stanimirovic, Jovana Nikolov, Ivan P. Stanimirovic:
  A generalization of Fibonacci and Lucas matrices. 2606-2619
• 
  Ana Luzón, Manuel A. Morón:
  Ultrametrics, Banach's fixed point theorem and the Riordan group. 2620-2635
• 
  Andreas Polyméris:
  Stability of two player game structures. 2636-2646
• 
  Hua Wang:
  The extremal values of the Wiener index of a tree with given degree sequence. 2647-2654
• 
  R. Julian R. Abel, Frank E. Bennett, Gennian Ge:
  Existence of directed triplewhist tournaments with the three person property 3PDTWh(v). 2655-2665
• 
  Jie Yan, Jianxing Yin:
  Constructions of optimal GDRP(n, lambda;v)'s of type lambda¹µ^m-1. 2666-2678
• 
  Ying Liu, Jia-Yu Shao, Xi-Ying Yuan:
  Some results on the ordering of the Laplacian spectral radii of unicyclic graphs. 2679-2697
• 
  Jesús Mario Bilbao, Julio Rodrigo Fernández García, N. Jiménez, J. J. López:
  Biprobabilistic values for bicooperative games. 2698-2711
• 
  Erfang Shan, T. C. Edwin Cheng, Liying Kang:
  An application of the Turán theorem to domination in graphs. 2712-2718
• 
  Alain Bretto, Luc Gillibert:
  G-graphs: An efficient tool for constructing symmetric and semisymmetric graphs. 2719-2739
• 
  Vojtech Bálint:
  A distance approximating trees. 2740-2752
• 
  Joel Ratsaby:
  Constrained versions of Sauer's lemma. 2753-2767
• 
  Michaël Rao:
  Solving some NP-complete problems using split decomposition. 2768-2780
• 
  Eva Yu-Ping Deng, Wei-Jun Yan:
  Some identities on the Catalan, Motzkin and Schröder numbers. 2781-2789

Notes

• 
  Xueliang Fu, Yuansheng Yang, Baoqi Jiang:
  A note on the signed edge domination number in graphs. 2790-2792
• 
  Weiping Wang, Tian-ming Wang:
  Identities via Bell matrix and Fibonacci matrix. 2793-2803
• 
  Yangkok Kim, Jaechil Yoo:
  An algorithm for constructing magic squares. 2804-2809
• 
  Edward G. Coffman Jr., János Csirik, Lajos Rónyai, Ambrus Zsbán:
  Random-order bin packing. 2810-2816
• 
  Heping Zhang, Shoujun Xu:
  None of the coronoid systems can be isometrically embedded into a hypercube. 2817-2822

Communications

• 
  Richard C. Brewster, Timothy Graves:
  On the restricted homomorphism problem. 2823-2826

Volume 156, Number 15, August 2008

• 
  Camino Balbuena, Yuqing Lin, Mirka Miller:
  Diameter-sufficient conditions for a graph to be super-restricted connected. 2827-2834
• 
  David Kuo, Jing-Ho Yan:
  The profile of the Cartesian product of graphs. 2835-2845
• 
  Sanming Zhou:
  A distance-labelling problem for hypercubes. 2846-2854
• 
  Rolf Bardeli, Michael Clausen, Andreas Ribbrock:
  A covering problem that is easy for trees but I-complete for trivalent graphs. 2855-2866
• 
  Shih-Hu Chiang, Jing-Ho Yan:
  On L(d, 1)-labeling of Cartesian product of a cycle and a path. 2867-2881
• 
  Kannan Balakrishnan, Manoj Changat, Sandi Klavzar:
  The median function on graphs with bounded profiles. 2882-2889
• 
  Justo Puerto, Arie Tamir, Juan A. Mesa, Dionisio Pérez-Brito:
  Center location problems on tree graphs with subtree-shaped customers. 2890-2910
• 
  Thomas Erlebach, Stamatis Stefanakos:
  Routing to reduce the cost of wavelength conversion. 2911-2923
• 
  Jørgen Bang-Jensen, Anders Yeo:
  The minimum spanning strong subdigraph problem is fixed parameter tractable. 2924-2929
• 
  Shoujun Xu, Heping Zhang:
  The Hosoya polynomial decomposition for catacondensed benzenoid graphs. 2930-2938
• 
  Eddie Cheng, Marc J. Lipman, László Lipták:
  Strong structural properties of unidirectional star graphs. 2939-2949
• 
  Jin-Hui Fang, Yong-Gao Chen:
  On a conjecture of Erdös, Graham and Spencer, II. 2950-2958
• 
  Robert W. Irving, David F. Manlove, Sandy Scott:
  The stable marriage problem with master preference lists. 2959-2977
• 
  Wai Chee Shiu:
  Extremal Hosoya index and Merrifield-Simmons index of hexagonal spiders. 2978-2985
• 
  Iliya Bouyukliev, Valentin P. Bakoev:
  A method for efficiently computing the number of codewords of fixed weights in linear codes. 2986-3004
• 
  Maria Bras-Amorós, Michael E. O'Sullivan:
  Redundancies of correction capability optimized Reed-Muller codes. 3005-3010
• 
  Jean Cousty, Michel Couprie, Laurent Najman, Gilles Bertrand:
  Weighted fusion graphs: Merging properties and watersheds. 3011-3027
• 
  Yufa Shen, Wenjie He, Xue Li, Donghong He, Xiaojing Yang:
  On hamiltonian colorings for some graphs. 3028-3034
• 
  Zhi-Guo Deng, Bao-Gen Xu:
  The Independence Number for De Bruijn networks and Kautz networks. 3035-3039
• 
  Sheng-Liang Yang:
  Jordan canonical form of Pascal-type matrices via sequences of binomial type. 3040-3045
• 
  Erdal Erel, Jay B. Ghosh:
  FPTAS for half-products minimization with scheduling applications. 3046-3056
• 
  Tetsuya Ishizeki, Yota Otachi, Koichi Yamazaki:
  An improved algorithm for the longest induced path problem on k-chordal graphs. 3057-3059
• 
  Domingos Moreira Cardoso, J. Orestes Cerdeira, Charles Delorme, Pedro C. Silva:
  Efficient edge domination in regular graphs. 3060-3065
• 
  Reza Saei, Seyed Mahmoud Sheikholeslami:
  Signed star k-subdomination numbers in graphs. 3066-3070

Volume 156, Number 16, September 2008

• 
  María Isabel González Vasco, Rainer Steinwandt:
  Applications of algebra to cryptography. 3071
• 
  Juan González-Meneses, Volker Gebhardt:
  On the cycling operation in braid groups. 3072-3090
• 
  Patrick Dehornoy:
  Efficient solutions to the braid isotopy problem. 3091-3112
• 
  Steven D. Galbraith, Kenneth G. Paterson, Nigel P. Smart:
  Pairings for cryptographers. 3113-3121
• 
  Alice Silverberg:
  Applications to cryptography of twisting commutative algebraic groups. 3122-3138
• 
  Rüdiger Sparr, Ralph Wernsdorf:
  Group theoretic properties of Rijndael-like ciphers. 3139-3149
• 
  Sidney W. Graham, Igor E. Shparlinski:
  On RSA moduli with almost half of the bits prescribed. 3150-3154

Volume 156, Number 17, October 2008

• 
  Ulrich Faigle, Bert Randerath, Rainer Schrader:
  Preface for CTW2005 special issue. 3155
• 
  M. Reza Emamy-Khansary, Martin Ziegler:
  On the coverings of the d-cube for d<=6. 3156-3165
• 
  Henning Fernau:
  Parameterized algorithmics for linear arrangement problems. 3166-3177
• 
  Athula Gunawardena, Robert R. Meyer:
  Discrete approximations to real-valued leaf sequencing problems in radiation therapy. 3178-3186
• 
  Anders Hansson, Gabriel Istrate:
  Counting preimages of TCP reordering patterns. 3187-3193
• 
  Martin Lätsch, Britta Peis:
  On a relation between the domination number and a strongly connected bidirection of an undirected graph. 3194-3202
• 
  Martin Charles Golumbic, Marina Lipshteyn, Michal Stern:
  Equivalences and the complete hierarchy of intersection graphs of paths in a tree. 3203-3215
• 
  Paulo Renato da Costa Pereira, Lilian Markenzon, Oswaldo Vernet:
  A clique-difference encoding scheme for labelled k-path graphs. 3216-3222
• 
  Isabel Méndez-Díaz, Paula Zabala, Abilio Lucena:
  A new formulation for the Traveling Deliveryman Problem. 3223-3237
• 
  Hagai Glicksman, Michal Penn:
  Approximation algorithms for group prize-collecting and location-routing problems. 3238-3247
• 
  Federico Malucelli, Stefano Pallottino, Daniele Pretolani:
  The stack loading and unloading problem. 3248-3266
• 
  Alain Quilliot:
  Preemptive scheduling and antichain polyhedra. 3267-3275
• 
  Eynat Rafalin, Diane L. Souvaine:
  Topological sweep of the complete graph. 3276-3290
• 
  Ingo Schiermeyer:
  Efficiency in exponential time for domination-type problems. 3291-3297
• 
  Sven Oliver Krumke, Dirk Räbiger, Rainer Schrader:
  Semi-preemptive routing on trees. 3298-3304
• 
  Daniel Král, Jirí Sgall, Tomás Tichý:
  Randomized strategies for the plurality problem. 3305-3311
• 
  Xuehou Tan:
  An efficient algorithm for the three-guard problem. 3312-3324
• 
  Angelika Hellwig, Lutz Volkmann:
  The connectivity of a graph and its complement. 3325-3328
• 
  Annegret Wagler:
  Constructions for normal graphs and some consequences. 3329-3338

Volume 156, Number 18, November 2008

• 
  Shinya Fujita, Tomoki Nakamigawa:
  Balanced decomposition of a vertex-colored graph. 3339-3344
• 
  Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier:
  Closest 4-leaf power is fixed-parameter tractable. 3345-3361
• 
  Anne Desideri Bracco, Ann Marie Natividad, Patrick Solé:
  On quintic quasi-cyclic codes. 3362-3375
• 
  Santosh N. Kabadi, Ramaswamy Chandrasekaran, K. P. K. Nair, Yash P. Aneja:
  Integer version of the multipath flow network synthesis problem. 3376-3399
• 
  Mathieu Liedloff, Ton Kloks, Jiping Liu, Sheng-Lung Peng:
  Efficient algorithms for Roman domination on some classes of graphs. 3400-3415
• 
  Tero Harju, Chang Li, Ion Petre:
  Graph theoretic approach to parallel gene assembly. 3416-3429
• 
  Evangelos Kranakis, Tim Mott, Ladislav Stacho:
  Constant memory routing in quasi-planar and quasi-polyhedral graphs. 3430-3442
• 
  Enrique Bendito, Ángeles Carmona, Andrés M. Encinas:
  Boundary value problems on weighted networks. 3443-3463
• 
  Rudolf Ahlswede, Harout K. Aydinian:
  On diagnosability of large multiprocessor networks. 3464-3474
• 
  Fu-Hsing Wang:
  An efficient distributed algorithm for canonical labeling on directed split-stars. 3475-3482
• 
  Edwin R. van Dam:
  Two-dimensional minimax Latin hypercube designs. 3483-3493
• 
  Giulia Galbiati:
  The complexity of a minimum reload cost diameter problem. 3494-3497
• 
  Bruno Gaujal, Jean Mairesse:
  Minimization of circuit registers: Retiming revisited. 3498-3505
• 
  Marc Bezem, Robert Nieuwenhuis, Enric Rodríguez-Carbonell:
  Exponential behaviour of the Butkovic-Zimmermann algorithm for solving two-sided linear systems in max-algebra. 3506-3509
• 
  Rudi Pendavingh, Quintijn Puite, Gerhard J. Woeginger:
  2-piercings via graph theory. 3510-3512
• 
  Amitabha Tripathi, Himanshu Tyagi:
  A simple criterion on degree sequences of graphs. 3513-3517
• 
  Orest Bucicovschi, Sebastian M. Cioaba:
  The minimum degree distance of graphs of given order and size. 3518-3521
• 
  Suh-Ryung Kim, Yoshio Sano:
  The competition numbers of complete tripartite graphs. 3522-3524
• 
  Ben D. MacArthur, Rubén J. Sánchez-García, James W. Anderson:
  Symmetry in complex networks. 3525-3531