Abstract Milling with Turn Costs

Details Abstract Milling with Turn Costs Abstract Milling with Turn Costs

2009-12-05

arxiv.org/abs/0912.1050v1

Computer Science

Computational Complexity

18 pages, 2 figures

Scientific paper

The Abstract Milling problem is a natural and quite general graph-theoretic model for geometric milling problems. Given a graph, one asks for a walk that covers all its vertices with a minimum number of turns, as specified in the graph model by a 0/1 turncost function fx at each vertex x giving, for each ordered pair of edges (e,f) incident at x, the turn cost at x of a walk that enters the vertex on edge e and departs on edge f. We describe an initial study of the parameterized complexity of the problem. Our main positive result shows that Abstract Milling, parameterized by: number of turns, treewidth and maximum degree, is fixed-parameter tractable, We also show that Abstract Milling parameterized by (only) the number of turns and the pathwidth, is hard for W[1] -- one of the few parameterized intractability results for bounded pathwidth.

Affiliated with

Also associated with

No associations

Rating

Abstract Milling with Turn Costs 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 Abstract Milling with Turn Costs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Abstract Milling with Turn Costs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-83507