Simple Cuts Are Fast and Good: Optimum Right-Angled Cuts in Solid Grids

DOI10.1007/978-3-642-17458-2_2MaRDI QIDQ3066140zbMATH OpenOpenAlexFDO

Authors Andreas Emil Feldmann, Shantanu Das, Peter Widmayer

Publication date 8 January 2011

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17458-2_2

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Corner cuts are close to optimal: from solid grids to polygons and back
• Simplest optimal cutting patterns for equal rectangles
• On optimal cuts of hyperrectangles
• Optimal cutting directions and rectangle orientation algorithm
• scientific article; zbMATH DE number 166938
• Restricted cuts for bisections in solid grids: a proof via polygons
• Optimal deterministic algorithms for 2-d and 3-d shallow cuttings
• Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
• Efficient cuts in Lagrangean `relax-and-cut' schemes

Cited in

(5)

• Optimal cutting directions and rectangle orientation algorithm
• Corner cuts are close to optimal: from solid grids to polygons and back
• An \(\mathcal{O}(n^4)\) time algorithm to compute the bisection width of solid grid graphs
• Restricted cuts for bisections in solid grids: a proof via polygons
• The bisection width of grid graphs

This page was built for publication: Simple Cuts Are Fast and Good: Optimum Right-Angled Cuts in Solid Grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3066140)