A Brief Summary of Independent Set in Graph Theory
Posted: April 24, 2010 Filed under: Research | Tags: coloring problem, dominating set, graph, graph coloring, independent set, maximal independent set, maximum independent set, mis 1 Comment »Graph Basics
Let G be a undirected graph. G=(V,E), where V is a set of vertices and E is a set of edges. Every edge e in E consists of two vertices in V of G. It is said to connect, join, or link the two vertices (or end points).
Independent Set
An independent set S is a subset of V in G such that no two vertices in S are adjacent. I suppose that its name is meaning that vertices in an independent set S is independent on a set of edges in a graph G. Like other vertex sets in graph theory, independent set has maximal and maximum sets as follows:
The independent set S is maximal if S is not a proper subset of any independent set of G.
The independent set S is maximum if there is no other independent set has more vertices than S.
That is, a largest maximal independent set is called a maximum independent set. The maximum independent set problem is an NP-hard optimization problem.
All graphs has independent sets. For a graph G having a maximum independent set, the independence number α(G) is determined by the cardinality of a maximum independent set.
Relations to Dominating Sets
- A dominating set in a graph G is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge.
- In other words, a vertex set D is a dominating set in G if and if only every vertex in a graph G is contained in (or is adjacent to) a vertex in D.
- Every maximal independent set S of vertices in a simple graph G has the property that every vertex of the graph either is contained in S or is adjacent to a vertex in S.
- That is, an independent set is a dominating set if and if only it is a maximal independent set.
Relations to Graph Coloring
- Independent set problem is related to coloring problem since vertices in an independent set can have the same color.
References
- Chapter 10, Graph Theory: Modeling, Applications, and Algorithms
- http://en.wikipedia.org/wiki/Independent_set_(graph_theory)
- http://en.wikipedia.org/wiki/Dominating_set
Data-Intensive Text Processing with MapReduce Draft Available in Online
Posted: March 11, 2010 Filed under: News, Research | Tags: data intensive, graph, hadoop, mapreduce, text processing Leave a comment »Data-Intensive Text Processing with MapReduce, Jimmy Lin and Chris Dyer
Actually, there have never been books that directly deal with MapReduce programming and algorithms. This book addresses from MapReduce algorithm design to EM Algorithms for Text Processing. Although this book is still draft, it seems well-organized and very interesting. In addition, the book contains some basic graph algorithms using MapReduce.
How to Create A Table in HBase for Beginners
Posted: November 27, 2009 Filed under: FOSS, Research | Tags: create table, hadoop, hbase, table, tutorial 7 Comments »I have accumulated some knowledge and know-how about MapReduce, Hadoop, and HBase since I participated in some projects. From hence, I’ll post the know-how of HBase by period. Today, I’m going to introduce a way to make a hbase table in java.
HBase provides two ways to allow a Hbase client to connect HBase master. One is to use a instance of HBaseAdmin class. HBaseAdmin provides some methods for creating, modifying, and deleting tables and column families. Another way is to use an instance of HTable class. This class almost provides some methods to manipulate data like inserting, modifying, and deleting rows and cells.
Thus, in order to make a hbase table, we need to connect a HBase master by initializing a instance of HBaseAdmin like line 4. HBaseAdmin requires an instance of HBaseConfiguration. If necessary, you may set some configurations like line 2.
In order to describe HBase schema, we make an instances of HColumnDescriptor for each column family. In addition to column family names, HColumnDescriptor enables you to set various parameters, such as maxVersions, compression type, timeToLive, and bloomFilter. Then, we can create a HBase table by invoking createTable like line 10.
HBaseConfiguration conf = new HBaseConfiguration();
conf.set("hbase.master","localhost:60000");
HBaseAdmin hbase = new HBaseAdmin(conf);
HTableDescriptor desc = new HTableDescriptor("TEST");
HColumnDescriptor meta = new HColumnDescriptor("personal".getBytes());
HColumnDescriptor prefix = new HColumnDescriptor("account".getBytes());
desc.addFamily(meta);
desc.addFamily(prefix);
hbase.createTable(desc);
Finally, you can check your hbase table as the following commands.
c0d3h4ck@code:~/Development/hbase$ bin/hbase shell HBase Shell; enter 'help<RETURN>' for list of supported commands. Version: 0.20.1, r822817, Wed Oct 7 11:55:42 PDT 2009 hbase(main):001:0> list TEST 1 row(s) in 0.0940 seconds
