{"entities":{"Q1270816":{"pageid":1281566,"ns":120,"title":"Item:Q1270816","lastrevid":68685747,"modified":"2026-04-13T01:25:47Z","type":"item","id":"Q1270816","labels":{"en":{"language":"en","value":"Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1218504"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$D984F6DD-E17B-443E-9549-0A959C117763","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d9d0b511b3d0eadce32725e815ec39c461acc63a","datavalue":{"value":{"text":"Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1270816$0A295542-E217-4A15-B93C-B0E64C36179A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5e964ad4b7444997c2a79524c4366a6445a296c6","datavalue":{"value":"0906.05067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270816$1C05E620-7E58-4C33-8B19-EC0D9DEA27F1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8bb8dd9126ee422946ef3f53e42b2c79f3927d11","datavalue":{"value":"10.1016/S0166-218X(98)00039-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270816$E78B330F-1408-4D40-81AA-EAA0DD993105","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$E80D526C-D099-4D24-9B0C-6EB7E80B89C6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b1001c55d7d9b1f13a0b1df5dbb73264773e01cb","datavalue":{"value":{"time":"+1999-02-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1270816$CBEE364A-4C06-448B-9DD7-E41E4F61CDFE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q1270816$6210D2C8-3DDA-442D-9593-4B8DA6BF1A54","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0b543487639cd922d76013dac2bfa76831d3a9bb","datavalue":{"value":"A bipartite graph is domino-free if it does not contain a 6-cycle with exactly one chord. Bipartite domino-free graphs can be recognized in time \\(O(nm)\\). A biclique cover (biclique decomposition) of a graph \\(G\\) is a family of complete bipartite subgraphs of \\(G\\) whose edges cover (partition) the edge set of \\(G\\). The minimum cardinalities of a biclique cover and a biclique partition of \\(G\\) are denoted by \\(\\text{s-dim}(G)\\) and \\(\\text{s-part}(G)\\), respectively. For bipartite domino-free graphs both parameters coincide and can be computed in time \\(O(nm)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270816$8BED3C35-3056-4E56-B763-7AC7E047CECF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270816$C7BCF528-3574-4831-B6D1-691A2396531C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270816$9D88B407-6B58-46DD-AD7F-9A96C7220CCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270816$FAD6E339-DD73-4136-9E33-50C9897423B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270816$979E87EC-99DF-4EC9-8D03-F0343CA974E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270816$E050F857-8270-47F4-B127-87D90E436361","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ce059dfca601fd03b8dd8647b0a35f9d9c83fc00","datavalue":{"value":"1218504","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270816$02E7C910-AABC-4FD0-A86E-B22EFE5D7AD3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2640b3f41a7aa570a8f30372d87da740cc5e9d31","datavalue":{"value":"biclique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270816$81B20C90-CB07-4382-B2D4-C8D8A58AEA6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270816$7D71972D-781D-4057-9C5D-DCC9D8DFC3C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea2fe13d487cee6b1e9a41271978549a7fa2de79","datavalue":{"value":"biclique cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270816$8B230B8C-82E2-432A-9E5D-77D28F94EAD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e04f98155861844755063e3ff18f219a91b2bab","datavalue":{"value":"bipartite domino-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270816$96EF8D78-A0BC-4DB0-AEC1-E3FA5B8D9D0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d9387e408da6a8875071fe878f39e88aafc7960","datavalue":{"value":"Galois lattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270816$EED738E6-2B44-4E7D-9F59-AAC5501CC2D6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5c302e7f4e0051cdca86fe6b90373e16108cfcb4","datavalue":{"value":{"entity-type":"item","numeric-id":236283,"id":"Q236283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$930B209E-02AB-49C0-AC44-32E77BDD7A60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"253b603fdda001d2bf12ed6bcc4bc6e9b265ee0d","datavalue":{"value":{"entity-type":"item","numeric-id":686484,"id":"Q686484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$3332343A-A935-48AD-BCDF-E9FAD9A2E5F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0162bd9262032c2ddf735175775bd701a986583a","datavalue":{"value":{"entity-type":"item","numeric-id":845721,"id":"Q845721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$8B8EF1C0-71B7-4871-B414-C154A9CE6CEB","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$A66F162D-6466-4934-A856-A1AC292911A2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"beafd09c79dfa9f43f527c7e484481f6934843d2","datavalue":{"value":{"entity-type":"item","numeric-id":3056948,"id":"Q3056948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$967CB5EC-CBA8-45AF-BC8C-8757ECF39C94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96c3586d0c57c7858660944bedd2ac17bc892e65","datavalue":{"value":{"entity-type":"item","numeric-id":1270816,"id":"Q1270816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$CD9FB429-37AA-4CD5-9E97-76E336F7C84B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e24dc6a7897959c528907c31c3df0e143c5919fb","datavalue":{"value":{"entity-type":"item","numeric-id":3029054,"id":"Q3029054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$023F955D-4DC1-4C8F-9D0C-94B22EF21B0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"260c22fcc0b2b8fe73e22a5fc6d05d81b513177a","datavalue":{"value":{"entity-type":"item","numeric-id":1126290,"id":"Q1126290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$B3796AF0-03C6-45AD-97E9-4CCD1FD50F41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb6e13b01334a8895ec53aaa8e925d98b84175c9","datavalue":{"value":{"entity-type":"item","numeric-id":3719852,"id":"Q3719852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$0038A8AE-3CAF-428B-B7B6-8B8764325BF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d61ad7cf38c4e431d541751b08c13839406163c5","datavalue":{"value":{"entity-type":"item","numeric-id":1357114,"id":"Q1357114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$D1E7A1EF-5606-4F6F-8CA4-99263C159D8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e78d7d44652f20c2a60f72580420d04a08808e1","datavalue":{"value":{"entity-type":"item","numeric-id":4277533,"id":"Q4277533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$42F25267-7288-468E-8849-2F052A8F7532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60e9b00fe16bc121f8312d916d237c3fe83869de","datavalue":{"value":{"entity-type":"item","numeric-id":672487,"id":"Q672487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$A1C42DE3-74A6-46F1-AEA9-DE479C3C904C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9481b55444254966d692d3a46c47e2d1179f5b63","datavalue":{"value":{"entity-type":"item","numeric-id":3797213,"id":"Q3797213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$D1C171DF-3B6D-4007-9019-CC2FEB8C54F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dfe9773a6753a6e178874d42722b35be775e311","datavalue":{"value":{"entity-type":"item","numeric-id":3031946,"id":"Q3031946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$8C3F4418-6E97-4BB7-8B97-485D576E9BBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d718fa34b00d42935bdfbe3669191e33cebeedc","datavalue":{"value":{"entity-type":"item","numeric-id":1186133,"id":"Q1186133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$2834AC4F-F8F9-4C03-BC5B-A73262F2BD56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a80dbd2d65fb34011bf925626c95b6d7b18f3cd","datavalue":{"value":{"entity-type":"item","numeric-id":1325959,"id":"Q1325959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$5D27859D-4793-48FC-B44B-DE4B15BE3F75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45afd92774d320e3507b8930999dd9e2ad5359e2","datavalue":{"value":{"entity-type":"item","numeric-id":1910576,"id":"Q1910576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$6C31C8E0-3DB3-47DD-96AF-6C7CB601DEEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fdf5b8cde129dad7b1f19100a2902cfe3c73387","datavalue":{"value":{"entity-type":"item","numeric-id":1252795,"id":"Q1252795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$1C2E92D0-D95E-4F07-A3F2-9BDE87C5623C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26b5d56f73427208d3f5d523e4ad9ec50dc5129e","datavalue":{"value":{"entity-type":"item","numeric-id":3952147,"id":"Q3952147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270816$9F2C8E04-8A4F-402E-A257-6E6A85B050AB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a18e3502d4fead3146b6c9eacc24714cf2a9e38e","datavalue":{"value":"W2065163038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270816$836AA059-71A7-4633-BBE7-FEDB5F4E4687","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"952fa3ea4d4cf9d665aa2aa912b1ecc8a11bba15","datavalue":{"value":{"entity-type":"item","numeric-id":1019181,"id":"Q1019181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1db6109b82a910d0f7178c65af545b437855c96","datavalue":{"value":{"amount":"+0.790406346321106","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1270816$3F96E120-2A75-456D-9645-DF4E240466B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8120f36c500cbbdae78d2b3393919634300e2b91","datavalue":{"value":{"entity-type":"item","numeric-id":3620683,"id":"Q3620683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"170a728880480a5bc43e7f7dfeded5f1d40006f0","datavalue":{"value":{"amount":"+0.7877660989761353","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1270816$9363BAD8-6DFF-413A-A0D5-8FF4E022F3B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"969b73319ecfebdcd0bc335b58d6a1f5497cc04f","datavalue":{"value":{"entity-type":"item","numeric-id":5458846,"id":"Q5458846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa4c1f064460fca806f1d2875d15e76482e5f0b2","datavalue":{"value":{"amount":"+0.7663026452064514","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1270816$FDDDB23E-A93D-4837-A925-D953F1FC1CCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c0e76bd68f088e3675229ee875bf78bff14ae86","datavalue":{"value":{"entity-type":"item","numeric-id":4691865,"id":"Q4691865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f90fd8f01c0139e4f691b535f6a6a8a8bae364ee","datavalue":{"value":{"amount":"+0.7561458349227905","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1270816$C11DCB31-9694-4E5C-A973-FD60CF0AF79C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"700c92a4f0fc7a68f1c4c411ff683ab4c9a5875b","datavalue":{"value":{"entity-type":"item","numeric-id":5369785,"id":"Q5369785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87a2250eed7695d0ba35e543c10a74d90fe4124d","datavalue":{"value":{"amount":"+0.7528075575828552","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1270816$CAB613D0-59EB-43F1-809A-9ED4D470BCAB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_of_minimum_biclique_cover_and_minimum_biclique_decomposition_for_bipartite_domino-free_graphs"}}}}}