{"entities":{"Q802577":{"pageid":804425,"ns":120,"title":"Item:Q802577","lastrevid":64488774,"modified":"2026-04-11T20:13:16Z","type":"item","id":"Q802577","labels":{"en":{"language":"en","value":"Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3891420"}},"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":"Q802577$4FD508C5-EAFE-4A42-98D9-92068C2C320D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"afb3648b3e190102e83217c6ad35055adcc09d87","datavalue":{"value":{"text":"Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q802577$2CC2D686-464A-4458-853F-0F90B2C3C940","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"874290aec3a7e4c666e3fb1092c43736117cdf6f","datavalue":{"value":"0559.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802577$8D158917-A52B-465A-89F4-C4C2EBCEC620","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7a7654aeca3fb733848aba1cb54b82b15c1076a0","datavalue":{"value":"10.1007/BF02579163","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802577$E141C036-FB20-43E9-9CD2-CD71401150BA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$A1921EC8-8F8A-462B-B35F-64ADBBFF84F7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q802577$B21A82DC-B188-4562-8F01-7F6CA7C10D82","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fd315462ba2b0054115540953cdc4550d36b9068","datavalue":{"value":"The author proves that the edge set of an arbitrary graph G on n vertices can be covered by at most \\(n-[\\log_ 2n]+1\\) complete bipartite subgraphs of G. This result improves the upper bound of J. C. Bermond. If the weight of a subgraph is the number of its vertices, then the author proves that there always exists a cover with total weight \\(c(n^ 2/\\log n)\\) and this bound is best possible apart from a constant factor. This result is a corollary to a more general theorem of the paper which solves a complexity problem of T. G. Tarj\u00e1n.","type":"string"},"datatype":"string"},"type":"statement","id":"Q802577$4ABA5173-244C-4639-9554-B0565F648CA8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"909a869c1ecf794f753a10fd07ee5fc43d30bc74","datavalue":{"value":{"entity-type":"item","numeric-id":594903,"id":"Q594903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$A21ABB2D-F477-4F3A-8BD7-E3CBD48733E5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802577$5CA3E6FD-D6BB-4050-A5CC-B446E81913DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802577$775FAADE-4D68-40AF-A807-B0309F2CB8C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"772466e23f65811e4792a58a12ff09d79c338e5f","datavalue":{"value":"05B20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802577$A24FDE9E-4875-441F-A076-96141E9C2D33","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7ce6438e8f6af045d1369393f2060526d4979983","datavalue":{"value":"3891420","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802577$DD73B577-3EBE-4367-AC4D-FABF5409358A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95315580a488697753f314bcf92d6e8b4a36f135","datavalue":{"value":"vertex covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q802577$E9E26F51-590D-4B3F-B9CF-C45EECA85263","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0462608a270ee74023a049798a00ea6109cc187d","datavalue":{"value":"covering by complete bipartite subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q802577$DBBD0C65-62FA-4529-96B5-F29312EC1E3C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"17fcd7139afa5567c823530fba22122acb06092a","datavalue":{"value":{"entity-type":"item","numeric-id":175498,"id":"Q175498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$45369ADE-2EAA-4BE1-8851-A28930F34C06","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":"Q802577$5E89E471-F88E-4B9F-ACB5-DAB32D6AA26B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c62594ef1ea9514c3144b6b09c5975a99cbda73f","datavalue":{"value":{"entity-type":"item","numeric-id":4088852,"id":"Q4088852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$6B0073C4-DAA6-4DFF-A07D-332A33F84EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"962bfe016847077cfb617ffdd441f5087ad5edd8","datavalue":{"value":{"entity-type":"item","numeric-id":1147719,"id":"Q1147719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$3D459518-A4D8-45FB-BD5F-BCE4827AD623","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b91fb34b309a1448e42736f924e3a5012ab649","datavalue":{"value":{"entity-type":"item","numeric-id":3253064,"id":"Q3253064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$88B11A9B-2240-473B-8B44-B14DDA105EED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c867b0d18c5229cdc2ec1ab76ab40ab92d3fd53e","datavalue":{"value":{"entity-type":"item","numeric-id":5512009,"id":"Q5512009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$EA571147-0E13-49D7-9D4E-7E40D403CD44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b9df05cfadd429c919e2c6f49687688f6d1327d","datavalue":{"value":{"entity-type":"item","numeric-id":5759552,"id":"Q5759552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$33F40D68-D3AA-4CB7-9307-D922C17B6823","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8dfac9344fb01c3b6cf8ffb4cfd5de147b769e2","datavalue":{"value":{"entity-type":"item","numeric-id":1247981,"id":"Q1247981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$04920829-8231-48D5-AF8A-7E703FA17441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8477d259cb3c7fd6ba0de3ee5367658997f4975c","datavalue":{"value":{"entity-type":"item","numeric-id":3912624,"id":"Q3912624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$A0A175E5-A7DE-48EA-AAD4-478FE83500D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6d666804f9c6b31e48af68187594e4d87829da9","datavalue":{"value":{"entity-type":"item","numeric-id":4154589,"id":"Q4154589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$45709867-8011-411E-9D4B-A5A396DE686D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f20709cce4ec714c605ba507cfbd28e51c9c018c","datavalue":{"value":{"entity-type":"item","numeric-id":3257129,"id":"Q3257129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$B7BA2EF7-2F4B-4BA8-AFED-FEC4AA635CA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"962af24ef35cbbdc08e38befed8abe47bf20d9f5","datavalue":{"value":{"entity-type":"item","numeric-id":5525916,"id":"Q5525916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$E67959C4-2983-4C1D-BCBA-594CB664EF5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6075b72a5540c2403053c6d9f599fac7a4be9766","datavalue":{"value":{"entity-type":"item","numeric-id":1838499,"id":"Q1838499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$AB560EB9-2F10-405B-968A-73D3E73CF8EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce9eb951e655494a595bee6fc576b501fffe29d5","datavalue":{"value":{"entity-type":"item","numeric-id":1171575,"id":"Q1171575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$47B6B69C-80F7-4835-AD64-786F748A4F6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9bb36bfa8ff9b999fd22009eb922d04862e30fb","datavalue":{"value":{"entity-type":"item","numeric-id":3967567,"id":"Q3967567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802577$6A8F2167-0846-4B36-975D-3F92E1A12028","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"993cb7ce2bf3cd4a60e7bbf1099184126f7c9b39","datavalue":{"value":{"entity-type":"item","numeric-id":1025967,"id":"Q1025967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1f366698296e65681929a4aaa0a754122b22bf8","datavalue":{"value":{"amount":"+0.8597362041473389","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":"Q802577$A143EF22-A6D8-4403-B464-F618EA49F168","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed11b97addd98b3e8041e3d48431c40486a16730","datavalue":{"value":{"entity-type":"item","numeric-id":4354593,"id":"Q4354593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae07eea69b041f7513f267b6c36bacb5f72935c5","datavalue":{"value":{"amount":"+0.8432422876358032","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":"Q802577$3FA334AD-E063-4EE9-9454-2FC9198673A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1177f00e36ae69085dda9ec47f251dbafdc09f8","datavalue":{"value":{"entity-type":"item","numeric-id":1363672,"id":"Q1363672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f8311b72ca8bcd6360bc4f1445da570726ee6fb","datavalue":{"value":{"amount":"+0.8301327228546143","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":"Q802577$AFE380D0-A79D-434A-A4B6-306212965771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2578eea6cd7035e857800f31de69233fc09b4712","datavalue":{"value":{"entity-type":"item","numeric-id":3312268,"id":"Q3312268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47cf001da9a4afb98b931190b835a205f306c300","datavalue":{"value":{"amount":"+0.8207748532295227","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":"Q802577$445856A5-7DBC-41A9-8A6D-8E553AEF7841","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":"73d6326d99c89fe029aa0f00483d6f229c0020ce","datavalue":{"value":{"amount":"+0.819878101348877","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":"Q802577$A495EF03-81ED-44B5-981D-865F9ADB6F27","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices","badges":[]}}}}}