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

DOI10.1137/0403010zbMath0689.68096OpenAlexW1982691959MaRDI QIDQ3031946

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

perfect graphsmin-max relationsBoolean basis problemrectangle cover problem

Mathematics Subject Classification ID

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

Related Items (7)

Unnamed Item ⋮ Approximation algorithms for decomposing octilinear polygons ⋮ On minimally non-firm binary matrices ⋮ FIXED PARAMETER ALGORITHMS FOR THE MINIMUM WEIGHT TRIANGULATION PROBLEM ⋮ A weighted min-max relation for intervals ⋮ Covering graphs with few complete bipartite subgraphs ⋮ Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs

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