The Boolean Basis Problem and How to Cover Some Polygons by Rectangles

DOI10.1137/0403010MaRDI QIDQ3031946zbMATH OpenOpenAlexFDO

Authors Anna Lubiw

Publication date 1990

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0403010

zbMATH Keywords

Boolean basis problemmin-max relationsperfect graphsrectangle cover problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Recommendations

• scientific article; zbMATH DE number 3872705
• Covering polygons with rectangles
• An algorithm for covering polygons with rectangles
• Experimental and Efficient Algorithms
• scientific article; zbMATH DE number 5291457
• Complexities of efficient solutions of rectilinear polygon cover problems
• Covering rectilinear polygons with axis-parallel rectangles
• Covering Rectilinear Polygons with Axis-Parallel Rectangles
• On rectangular covering problems
• scientific article; zbMATH DE number 4117851

Cited in

(8)

• Covering graphs with few complete bipartite subgraphs
• A weighted min-max relation for intervals
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Approximation algorithms for decomposing octilinear polygons
• Building a consensus: a rectangle covering problem
• FIXED PARAMETER ALGORITHMS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM
• Problems and invariants connected with bicliques and multicliques of graphs
• On minimally non-firm binary matrices

This page was built for publication: The Boolean Basis Problem and How to Cover Some Polygons by Rectangles

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