[
https://issues.apache.org/jira/browse/GIRAPH-157?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13291156#comment-13291156
]
Sebastian Schelter commented on GIRAPH-157:
-------------------------------------------
Eli,
the whole purpose of complexity theory is to identify the problems computable
in acceptable (polynomial) time on today's computers. Out of these problems
only those for which we know algorithms with linear runtime can be scaled to
very large datasets. I think you are wasting your time, if you implemented a
nonpolynomial algorithm.
You should ask yourself why you couldn't find a large graph where the chromatic
number is known, maybe it has something to do with the problem being
NP-complete???
> Vertex to perform graph coloring on simple, connected, undirected graphs and
> related test.
> ------------------------------------------------------------------------------------------
>
> Key: GIRAPH-157
> URL: https://issues.apache.org/jira/browse/GIRAPH-157
> Project: Giraph
> Issue Type: Test
> Components: examples, test
> Affects Versions: 0.2.0
> Reporter: Eli Reisman
> Assignee: Eli Reisman
> Priority: Trivial
> Labels: newbie
> Attachments: GIRAPH-157-2.patch, GIRAPH-157.patch
>
>
> Hi. I am attempting to learn the Hadoop and Giraph codebases and wanted to
> write a simple client application for Giraph to help me learn the ins and
> outs of it. This is a simple unit test and vertex modeled after the
> ConnectedComponentsVertex and related test. The vertex test runs whenever you
> run the "mvn test" or "mvn verify" suite of tests. When finished processing,
> each vertex will have an integer value that is its color.
> This is a pretty simple implementation, and although I have tested it on a
> number of small graphs of varied trickiness and it seems to rapidly arrive at
> a minimal coloring, its hard (for me at least) to guess which possible
> coloring it will arrive at and I have no idea how it will do on really big
> graphs yet without finding some more pre-colored larger test graphs to try it
> on. Ideas anyone?
> Anyway, it was fun to put this together, and I'd be happy to improve it or
> receive some help or advice to further the cause. Thanks again, I am hoping
> this will be the first of many (hopefully more useful) contributions!
> Eli
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:
https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
