A comparison of two approaches for polynomial time algorithms computing basic graph parameters

Details A comparison of two approaches for polynomial time algorithms computing basic graph parameters A comparison of two approaches for polynomial time algorithms computing basic graph parameters

2008-06-25

arxiv.org/abs/0806.4073v1

Computer Science

Data Structures and Algorithms

25 pages, 3 figures

Scientific paper

In this paper we compare and illustrate the algorithmic use of graphs of bounded tree-width and graphs of bounded clique-width. For this purpose we give polynomial time algorithms for computing the four basic graph parameters independence number, clique number, chromatic number, and clique covering number on a given tree structure of graphs of bounded tree-width and graphs of bounded clique-width in polynomial time. We also present linear time algorithms for computing the latter four basic graph parameters on trees, i.e. graphs of tree-width 1, and on co-graphs, i.e. graphs of clique-width at most 2.

Affiliated with

Also associated with

No associations

Rating

A comparison of two approaches for polynomial time algorithms computing basic graph parameters does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A comparison of two approaches for polynomial time algorithms computing basic graph parameters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A comparison of two approaches for polynomial time algorithms computing basic graph parameters will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-162612