Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
  1. Home
  2. Journals
  3. Combinatorics, Probability and Computing
  4. Volume 2
Journal Home
Refine listing

Refine listing

Access:
Publication date:

Actions for selected content:

Select all | Deselect all
  • View selected items
  • Export citations
  • Download PDF (zip)
  • Save to Kindle
  • Save to Dropbox
  • Save to Google Drive

Save Search

You can save your searches here and later view and run them again in "My saved searches".

Please provide a title, maximum of 40 characters.
Cancel
×
< Back to all issues

Volume 2 - December 1993

Contents

Page 3 of 3

Research Article

  • A Random Recolouring Method for Graphs and Hypergraphs

  • Colin McDiarmid
  • Published online by Cambridge University Press:
    12 September 2008, pp. 363-365

  • We consider a simple randomised algorithm that seeks a weak 2-colouring of a hypergraph H; that is, it tries to 2-colour the points of H so that no edge is monochromatic. If H has a particular well-behaved form of such a colouring, then the method is successful within expected number of iterations O(n3) when H has n points. In particular, when applied to a graph G with n nodes and chromatic number 3, the method yields a 2-colouring of the vertices such that no triangle is monochromatic in expected time O(n4).

  • Recognizing Polymatroids Associated with Hypergraphs

  • Dirk Vertigan, Geoff Whittle
  • Published online by Cambridge University Press:
    12 September 2008, pp. 519-530

  • Two natural classes of polymatroids can be associated with hypergraphs: the so-called Boolean and hypergraphic polymatroids. Boolean polymatroids carry virtually all the structure of hypergraphs; hypergraphic polymatroids generalize graphic matroids. This paper considers algorithmic problems associated with recognizing members of these classes. Let k be a fixed positive integer and assume that the k-polymatroid ρ is presented via a rank oracle. We present an algorithm that determines in polynomial time whether ρ is Boolean, and if it is, finds the hypergraph. We also give an algorithm that decides in polynomial time whether ρ is the hypergraphic polymatroid associated with a given hypergraph. Other structure-theoretic results are also given.

Front matter

  • CPC volume 2 issue 3 Cover and Front matter

  • Published online by Cambridge University Press:
    12 September 2008, pp. f1-f2
    • Article
      • You have access
    • PDF
    • Export citation

Author Index

Back matter

  • CPC volume 2 issue 3 Cover and Back matter

  • Published online by Cambridge University Press:
    12 September 2008, pp. b1-b2
    • Article
      • You have access
    • PDF
    • Export citation

Front matter

  • CPC volume 2 issue 4 Cover and Front matter

  • Published online by Cambridge University Press:
    12 September 2008, pp. f1-f2
    • Article
      • You have access
    • PDF
    • Export citation

Back matter

  • CPC volume 2 issue 4 Cover and Back matter

  • Published online by Cambridge University Press:
    12 September 2008, pp. b1-b2
    • Article
      • You have access
    • PDF
    • Export citation

Page 3 of 3