Results 1 to 2 of 2

Math Help - Online Coloring Known Graphs

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    2

    Online Coloring Known Graphs

    Hi,

    I have problems with understanding some terms and algorithms.

    I have a PDF with some dissertation (as in title) and I don't understand:
    • Why Alice reveals the color of vertex and how she computes is? And why she even colors them if Bob is supposed to give correct coloring?
      The same lower bound holds also for randomized algorithm against an oblivious
      adversary; in this version, Bob is allowed to base his color decisions on coin flips
      which are hidden from Alice. It also holds for a further restricted model, where Alice
      immediately commits a presented vertex to be a particular vertex in the underlying
      graph as soon as Bob decides on his color. This implies that Alice is eectively
      coloring the vertices online as well, and revealing those choices.
      Terminology We say that Bob assigns vertices to bins while Alice colors.The hue
      of a bin is the set of colors among the vertices in the bin. We say that progress is
      made on a vertex if the color assigned to that vertex increases the hue of the bin to
      which the vertex was assigned.
    • What means "oblivious" in context of that dissertation?
    • I don't understand what it has in common, ie. I think we should search for codes with Hamming distance > 3k/8.
      We call a collection dispersed if any pair of sets have at most 3k/8 elements in
      common. Thus, we seek a binary code of length k with Hamming distance k/4.
    • What's the difference between adaptive construction and oblivious construction?


    I've spent a few days trying to understand it.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2009
    Posts
    2
    Quote Originally Posted by zoska View Post
    Hi,

    I have problems with understanding some terms and algorithms.

    I have a PDF with some dissertation (as in title) and I don't understand:
    • Why Alice reveals the color of vertex and how she computes is? And why she even colors them if Bob is supposed to give correct coloring?

    • What means "oblivious" in context of that dissertation?
    • I don't understand what it has in common, ie. I think we should search for codes with Hamming distance > 3k/8.
    • What's the difference between adaptive construction and oblivious construction?


    I've spent a few days trying to understand it.
    EDIT:
    Sorry I forgot to put a link to PDFs:
    Index of /~tarsa/math
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph coloring
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 2nd 2010, 12:49 PM
  2. Graph coloring
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 1st 2010, 11:06 PM
  3. Coloring K10
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 15th 2009, 11:42 AM
  4. 4 Coloring Problems
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 22nd 2009, 08:32 PM
  5. Coloring of a Cube
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 9th 2008, 04:01 PM

Search Tags


/mathhelpforum @mathhelpforum