Combinatorica, Volume 15

Volume 15, Number 1, 1995

• Charles J. Colbourn, J. Scott Provan, Dirk Vertigan:
  The Complexity of Computing the Tutte Polynomial on Transversal Matroids. 1-10
  
• Persi Diaconis, Michael McGrath, Jim Pitman:
  Riffle Shuffles, Cycles, and Descents. 11-29
  
• Joel Friedman:
  Some Graphs with Small Second Eigenvalue. 31-42
  
• Joel Friedman, Avi Wigderson:
  On the Second Eigenvalue of Hypergraphs. 43-65
  
• Alan M. Frieze, Mark Jerrum:
  An Analysis of a Monte Carlo Algorithm for Estimating the Permanent. 67-83
  
• Hanno Lefmann, Vojtech Rödl:
  On Erdös-Rado Numbers. 85-104
  
• Klaus Metsch:
  On the Number of Lines in Planar Spaces. 105-110
  
• Moshe Morgenstern:
  Natural Bounded Concentrators. 111-122
  
• Gábor Tardos:
  Transversals of 2-Intervals, a Topological Approach. 123-134
  
• Dorothea Wagner, Karsten Weihe:
  A Linear-Time Algorithm for Edge-Disjoint Paths in Planar Graphs. 135-150
  

Volume 15, Number 2, 1995

• Timothy Y. Chow:
  Penny-Packings with Minimal Second Moments. 151-158
  
• Guoli Ding:
  Bounding the Number of Bases of a Matroid. 159-165
  
• György Elekes:
  Circle Grids and Bipartite Graphs of Distances. 167-174
  
• David A. Grable, Kevin T. Phelps, Vojtech Rödl:
  The Minimum Independence Number for Designs. 175-185
  
• Philip N. Klein, Satish Rao, Ajit Agrawal, R. Ravi:
  An Approximate Max-Flow Min-Cut Relation for Unidirected Multicommodity Flow, with Applications. 187-202
  
• Dror Lapidot, Adi Shamir:
  A One-Round, Two-Prover, Zero-Knowledge Protocol for NP. 204-214
  
• Nathan Linial, Eran London, Yuri Rabinovich:
  The Geometry of Graphs and Some of its Algorithmic Applications. 215-245
  
• Xiaoyun Lu:
  Hamiltonian Cycles in Bipartite Graphs. 247-254
  
• Alessandro Panconesi, Aravind Srinivasan:
  The Local Natur of Delta-Coloring and its Algorithmic Applications. 255-280
  
• Paul D. Seymour:
  Packing Directed Circuits Fractionally. 281-288
  
• D. A. Youngs:
  Minimal Orientations of Colour Critical Graphs. 289-295
  

• David Rubinstein:
  Sensitivity vs. Block Sensitivity of Boolean Functions. 297-299
  

Volume 15, Number 3, 1995

• Noga Alon, Moshe Dubiner:
  A Lattice Point Problem and Additive Number Theory. 301-309
  
• K. T. Arasu, James A. Davis, Jonathan Jedwab:
  A Nonexistence Result for Abelian Menon Difference Sets Using Perfect Binary Arrays. 311-317
  
• Jason Cooper, Nathan Linial:
  Fast Perfect-Information Leader-Election Protocols with Linear Immunity. 319-332
  
• Walter A. Deuber, Neil Hindman, Imre Leader, Hanno Lefmann:
  Infinite Partition Regular Matrices. 333-355
  
• Yoshimi Egawa, Katsuhiro Ota, Akira Saito, Xingxing Yu:
  Non-Contractible Edges in A 3-Connected Graph. 357-364
  
• Bernhard Herwig:
  Extending Partial Isomorphisms on Finite Structures. 365-371
  
• T. R. Jensen, F. Bruce Shepherd:
  Note on a Conjecture of Toft. 373-377
  
• Hanno Lefmann, Torsten Thiele:
  Point Sets with Distinct Distances. 379-408
  
• Jesús A. De Loera, Bernd Sturmfels, Rekha R. Thomas:
  Gröner Bases and Triangulations of the Second Hypersimplex. 409-424
  
• Serge A. Plotkin, Éva Tardos:
  Improved Bounds on the Max-Flow Min-Cut Ratio for Multicommodity Flows. 425-434
  
• David P. Williamson, Michel X. Goemans, Milena Mihail, Vijay V. Vazirani:
  A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems. 435-454
  

Volume 15, Number 4, 1995

• H. L. Abbott, D. R. Hare, Bing Zhou:
  Large Faces in 4-Critical Planar Graphs with Minimum Degree 4. 455-467
  
• H. L. Abbott, Bing Zhou:
  Some Remarks on (k-1)-Critical Subgraphs of k-Critical Graphs. 469-474
  
• Rudolf Ahlswede, Péter L. Erdös, Niall Graham:
  A Splitting Property of Maximal Antichains. 475-480
  
• Kris Coolsaet:
  Local Structure of Graphs with lambda = mu=2, alpha₂ = 4. 481-487
  
• Alan M. Frieze, Bruce A. Reed:
  Covering the Edges of a Random Graph by Cliques. 489-497
  
• Michel X. Goemans, V. S. Ramakrishnan:
  Minimizing Submodular Functions over Families of Sets. 499-513
  
• Satoru Iwata:
  Principal Structure of Submodular Systems and Hitchcock-Type Independent Flows. 515-532
  
• Wolfgang Mader:
  Existence of Vertices of Local Connectivity k in Digraphs of Large Outdegree. 533-539
  
• Bojan Mohar:
  Uniqueness and Minimality of Large Face-Width Embeddings of Graphs. 541-556
  
• Noam Nisan, Avi Wigderson:
  On Rank vs. Communication Complexity. 557-565
  
• Ran Raz, Boris Spieker:
  On the "Log Rank"-Conjecture in Communication Complexity. 567-588
  
• Vojtech Rödl, Norbert Sauer, Xu-Ding Zhu:
  Ramsey Families which Exclude a Graph. 589-596
  

Last update Sat May 18 20:10:44 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page