×

Milling a graph with turn costs: a parameterized complexity perspective. (English) Zbl 1309.68093

Thilikos, Dimitrios M. (ed.), Graph theoretic concepts in computer science. 36th international workshop, WG 2010, Zarós, Crete, Greece, June 28–30, 2010. Revised papers. Berlin: Springer (ISBN 978-3-642-16925-0/pbk). Lecture Notes in Computer Science 6410, 123-134 (2010).
Summary: The Discrete 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 \(f _{x }\) 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.
For the entire collection see [Zbl 1200.68024].

MSC:

68Q25 Analysis of algorithms and problem complexity
05C12 Distance in graphs
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arkin, E., Bender, M., Demaine, E., Fekete, S., Mitchell, J., Sethia, S.: Optimal covering tours with turn costs. SIAM J. Computing 35(3), 531–566 (2005) · Zbl 1122.90064
[2] Dorn, F., Penninkx, E., Bodlaender, H., Fomin, F.: Efficient exact algorithms on planar graphs: exploiting sphere cut branch decompositions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 95–106. Springer, Heidelberg (2005) · Zbl 1162.05354
[3] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
[4] Fellows, M., Fomin, F., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. In: Dress, A.W.M., Xu, Y., Zhu, B. (eds.) COCOA. LNCS, vol. 4616, pp. 366–377. Springer, Heidelberg (2007) · Zbl 1175.68292
[5] Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)
[6] Held, M.: On the Computational Geometry of Pocket Machining. LNCS, vol. 500. Springer, Heidelberg (1991) · Zbl 0755.68136
[7] Niedermeier, R.: Invitation to Fixed Parameter Algorithms, vol. 31. Oxford University Press, Oxford (2006) · Zbl 1095.68038
[8] Szeider, S.: Not so easy problems for tree decomposable graphs. In: International Conference on Discrete Mathematics (ICDM), pp. 161–171 (2008) (invited talk)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.