Re: A restricted case of graph coloring, is this a known problem?
- From: torbenm@xxxxxxxxxxxxx (Torben Ægidius Mogensen)
- Date: Mon, 26 Feb 2007 11:08:12 +0100
Chris F Clark <cfc@xxxxxxxxxxxxxxxxxxxx> writes:
I recently assign a set of summer intern candidates a problem that can
be solved by graph coloring, but all the students came up with n**2 or
n**3 solutions using a greedy approach.
Now, as I recall, general graph coloring is np-complete. So, the
question I need to have answered is whether I constrained this problem
to a set where it can be solved in polynomial time or whether the
students have simply found a partial solution.
Here is a quick sketch of the problem. You have two machines that you
run in a pipelined fashion. The first machine executes a translate
instruction (a linear map of values in the set to other values). The
second machine executes a DFA and returns whether it accepts or
rejects the input string. The goal is to minimze the size of states
in the DFA by remapping input characters (using the translation
machine) into a smaller input range.
For example, if the machine has transitions on the range a-f, we might
represent those characters by 1, then we might represent the range 0-9
by 2, and A-F by 3. and G-Z by 4, etc. Thus, instead of having lots
of similar transitions to the same state, we have a much smaller set
of transitions and a much smaller alphabet. If there are only 16
distinct ranges used in the DFA, we might use a 4 bit alphabet and
states would have at most 16 transitions.
The basic idea is you want to find sets of characters which always
make their transitions together. That is, for all states in the DFA,
if one character in the set makes a transition to some other state,
every other character in the set makes that same transition.
This can be represented as a graph coloring problem. [...]
It can also be represented as multiset discrimination, similar to DFA
minimization: Two characters are in different classes if there is a
transition that distinguishes them, otherwise they are in the same
class.
In the absense of cycles, multiset discrimination can be done in
linear time. In this case, the cycles in the DFA don't matter, as it
is not the states of the DFA we want to discriminate, but the
characters.
Torben
.
- References:
- A restricted case of graph coloring, is this a known problem?
- From: Chris F Clark
- A restricted case of graph coloring, is this a known problem?
- Prev by Date: Re: An efficient way of sequencing streams of integers
- Next by Date: Re: Do Write Once TM's Halt?
- Previous by thread: Re: A restricted case of graph coloring, is this a known problem?
- Next by thread: On the General Construction for Kleene star in Context-Free Language
- Index(es):
Relevant Pages
|
