Not So Easy Problems for Tree Decomposable Graphs

Details Not So Easy Problems for Tree Decomposable Graphs Not So Easy Problems for Tree Decomposable Graphs

2011-07-06

arxiv.org/abs/1107.1177v1

Ramanujan Mathematical Society, Lecture Notes Series no. 13, 2010, pp. 179-190

Computer Science

Data Structures and Algorithms

Author's self-archived copy

Scientific paper

We consider combinatorial problems that can be solved in polynomial time for graphs of bounded treewidth but where the order of the polynomial that bounds the running time is expected to depend on the treewidth bound. First we review some recent results for problems regarding list and equitable colorings, general factors, and generalized satisfiability. Second we establish a new hardness result for the problem of minimizing the maximum weighted outdegree for orientations of edge-weighted graphs of bounded treewidth.

Affiliated with

Also associated with

No associations

Rating

Not So Easy Problems for Tree Decomposable Graphs 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 Not So Easy Problems for Tree Decomposable Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Not So Easy Problems for Tree Decomposable Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-678735