{"entities":{"Q557825":{"pageid":559592,"ns":120,"title":"Item:Q557825","lastrevid":62730387,"modified":"2026-04-11T08:04:40Z","type":"item","id":"Q557825","labels":{"en":{"language":"en","value":"Generating bicliques of a graph in lexicographic order"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2184055"}},"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":"Q557825$28E73AF6-B746-425B-B276-8640BF795D3B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d153fd7ca9c830db2a81676cf1cbb2959dee1204","datavalue":{"value":{"text":"Generating bicliques of a graph in lexicographic order","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q557825$35E7DB37-E03B-41A2-99EC-5BB7FB56C3E7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d80b1b0d7b7d5d5892687d288c0c058c823468a3","datavalue":{"value":"1076.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557825$F161AA3E-418E-4C52-9592-3D448E30A45D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"549311b489aee32cdb4a128cedac53257a7e4051","datavalue":{"value":{"entity-type":"item","numeric-id":557824,"id":"Q557824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$5872B791-B540-4322-BB70-69F6EDFDD3F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8194275e4297e0d41e3cff3373ee47d709a37375","datavalue":{"value":{"entity-type":"item","numeric-id":1567274,"id":"Q1567274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$A5EE2F17-8A75-4DA7-A98A-677991121B46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fd683c02639d43389eac3b26f5a1a60d6fdb0bf1","datavalue":{"value":{"entity-type":"item","numeric-id":712274,"id":"Q712274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$82F54B68-09E8-498B-9059-ABA6432B6D24","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$3E9F971E-6A4B-4052-8EC2-EB47E007496D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3be35b99bc40d25914143aa31268a19fcdde1b9d","datavalue":{"value":{"time":"+2005-06-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q557825$6D87920E-2B0A-4072-9E5B-DA84AEE96BC3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0d924b440a70940dac583953ce2f2b87a9e6152d","datavalue":{"value":"A complete bipartite set \\(B\\) of a graph is a subset of vertices admitting a bipartition \\(B=X\\cup Y\\) such that both \\(X\\) and \\(Y\\) are independent sets and all vertices of \\(X\\) are adjacent to those of \\(Y\\). If both \\(X,Y\\neq \\emptyset\\), then \\(B\\) is called proper. A biclique is a maximal proper complete bipartite set of a graph. The authors present an algorithm that generates all bicliques of a graph in lexicographic order, with polynomial-time delay between the output of two successive bicliques. They show also that there is no polynomial-time delay algorithm for generating all bicliques in reverse lexicographic order, unless P=NP. The paper contains an extension of results of \\textit{D. S. Johnson, C. H. Papadimitriou} and \\textit{M. Yannakakis} [``On generating all maximal independent sets'', Inf. Process. Lett. 27, 119--123 (1988; Zbl 0654.68086)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q557825$DAF5412E-613D-4912-B322-C08CA236CC27","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7f1127c63fcb04479eae252afd6f073fe30fe10","datavalue":{"value":{"entity-type":"item","numeric-id":187117,"id":"Q187117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$37740ADE-AAF4-4A85-9E45-E54F5B64CA4D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557825$F102A1ED-E536-4055-BBA1-9DD4BA6FCA8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557825$986A6598-85E2-46E8-9419-36BB00CF20EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557825$7C4F00F9-B095-4CC0-895B-B05271CE664F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557825$7F6AB4EE-055B-4EC8-974F-24385F0E6AF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557825$641A11E6-B327-46D1-BC32-D755E575F116","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aae6cc46edc208d26c9dc0dc9689ca4114092475","datavalue":{"value":"2184055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557825$B764416F-B8ED-4772-A37F-D7B0CE9C239C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c985d8f8dc90c7bc35654f4f9143df0550cb5288","datavalue":{"value":"algorithmics","type":"string"},"datatype":"string"},"type":"statement","id":"Q557825$35CD8728-ECA2-49D4-9E88-9F307A52027A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2640b3f41a7aa570a8f30372d87da740cc5e9d31","datavalue":{"value":"biclique","type":"string"},"datatype":"string"},"type":"statement","id":"Q557825$88B5D398-D252-4670-BA06-11D1E3B915A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"816681eea21269f3ad56375e4f8d7d873b144eb6","datavalue":{"value":"enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q557825$0CEF60D5-D945-44A6-B052-5F88C033338B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q557825$13AD89A4-85D8-46F3-A323-94D1472FBE17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22683c06fedcaa7012c349358a0eb5ee9c463256","datavalue":{"value":"lexicographic order","type":"string"},"datatype":"string"},"type":"statement","id":"Q557825$9BABA002-E468-4717-B74D-2DDBD87970C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4dfbf029a00ea05f8874b2ac092078a7333a53da","datavalue":{"value":"polynomial-time delay","type":"string"},"datatype":"string"},"type":"statement","id":"Q557825$8D4B1A23-48DB-43FB-B355-626CF3251AE1","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":"Q557825$6D7398EF-A048-474B-B148-AFACE79974B6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3e770b58545df2e3f113effedf5b85575636c5d2","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2005.01.014","type":"string"},"datatype":"url"},"type":"statement","id":"Q557825$87537EDC-996F-4C87-B77F-C38EDCDEE5F7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"183e97272c63d7e5bd785d0729c1e43db4fb0512","datavalue":{"value":"W1979312971","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557825$523F595D-55F4-4500-ADDD-FC53689EA8E6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"754a4a60c3c7157ef3f839e3afcfc0210f97581a","datavalue":{"value":{"entity-type":"item","numeric-id":705493,"id":"Q705493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$E99196FB-23BD-4234-B5FA-9559CB618C09","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":"Q557825$0DB8086C-B596-41BB-AABE-194D287807BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf653ca76c03edd57ac2f36a85ddf24e5b51f007","datavalue":{"value":{"entity-type":"item","numeric-id":686243,"id":"Q686243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$9346CF52-5337-4DDE-B036-3752536B4637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf259006c74a21fb245a199f7433514fa529de9c","datavalue":{"value":{"entity-type":"item","numeric-id":2775896,"id":"Q2775896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$91DAA03C-648C-4499-BA6E-E9888326E61A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$D57C6105-B394-42AB-B4E9-9337CAD94BE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f41bc558acdabc32b8492268548c9e818697a7fa","datavalue":{"value":{"entity-type":"item","numeric-id":4198811,"id":"Q4198811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$AA7C3C99-AAFB-42B8-A401-9755C001C597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcd4a5d59a9b91f2e9f1f513e4264858083d7083","datavalue":{"value":{"entity-type":"item","numeric-id":4217307,"id":"Q4217307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$EA87DBD4-1F1A-4E75-A5BB-D14708904F2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5ba7598a622756daa7a1a98c7ec39119480164a","datavalue":{"value":{"entity-type":"item","numeric-id":1108809,"id":"Q1108809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$0A14DC77-E1A5-475F-A05A-F03F05D0D589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cee622c8004588ce4ee327462c9cddb2144c21dd","datavalue":{"value":{"entity-type":"item","numeric-id":3890128,"id":"Q3890128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$E062FDF5-4DC4-4709-91DC-95D203921798","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":"Q557825$8CA14C6A-22F9-40CD-8D47-D941F3C8038B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751581187d2b6c441c261ae33faafe5ee0321f46","datavalue":{"value":{"entity-type":"item","numeric-id":1414242,"id":"Q1414242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$E9DA3EFB-2018-490F-815B-26D966DB103B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7a5e61c140f53f63655fe2f128f05bb22d6abc2","datavalue":{"value":{"entity-type":"item","numeric-id":4373687,"id":"Q4373687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$0DA156C8-B7E6-474C-A55F-E1D6A8484C2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2e5a5b964e58a4c1b445c047d7344e912592d3d","datavalue":{"value":{"entity-type":"item","numeric-id":5932702,"id":"Q5932702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$00E58022-0BC6-4213-8E30-FE7E0E3C2F86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb85e2a08b123210f7ea1cf8a8c1c958121dd184","datavalue":{"value":{"entity-type":"item","numeric-id":4138754,"id":"Q4138754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$0CA45AB1-EE05-498B-A7CC-EF8C1D9815B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f17cfea272eff349cb6f6d9413633017b4480986","datavalue":{"value":{"entity-type":"item","numeric-id":802577,"id":"Q802577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$F8DEC1E1-A20E-4200-899C-AA24562D861C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53931acda4d1de6fffc8c785b472a64b77dbbda9","datavalue":{"value":{"entity-type":"item","numeric-id":5402565,"id":"Q5402565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557825$E6442822-BA9C-4DC3-8B44-07A7F5FAFD73","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1ffae706b6be4d38662f44748ff45db111705fa3","datavalue":{"value":"10.1016/J.TCS.2005.01.014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557825$912C391E-5B0D-485C-BC75-7534519E91BF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56c388b8b8fbfdb1516344af8178b558fec902af","datavalue":{"value":{"entity-type":"item","numeric-id":1108809,"id":"Q1108809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"249386ef32e94ed855cc3cf819f135d63f1101c5","datavalue":{"value":{"amount":"+0.850502073764801","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":"Q557825$5C5D6E15-AF1C-4A8D-BA59-F20D4F5E3B17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa0e4fabda074a343f63f0967c1a77cab8eba5c2","datavalue":{"value":{"entity-type":"item","numeric-id":5919931,"id":"Q5919931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f461076ddfdda9b05eba1881429968c2e90416a","datavalue":{"value":{"amount":"+0.8482596278190613","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":"Q557825$7C2266CA-A586-4C95-BF6D-7F3CA863B214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cadfa7a84726a8ad69c6dcd1c8bb328084948c30","datavalue":{"value":{"entity-type":"item","numeric-id":5302053,"id":"Q5302053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6cb90adc5fe2ff03d536b7d7972ed86e41f50cb","datavalue":{"value":{"amount":"+0.819132924079895","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":"Q557825$8A6AC850-B2B2-4755-92EF-5331250B3741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3341a2354f97f5e795e2e82727d3f7e0a62af28","datavalue":{"value":{"entity-type":"item","numeric-id":2428684,"id":"Q2428684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ab5f0dc9006b6deb00cf8d840db5c4572478695","datavalue":{"value":{"amount":"+0.8087900876998901","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":"Q557825$7DC2B4AF-3A19-4C93-9516-3E8983CE5A86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c9e4e0c8e1847e55dd8f1a6fab2dc23883322e4","datavalue":{"value":{"entity-type":"item","numeric-id":3990622,"id":"Q3990622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bbc04a871ab8ccba13074a0d63da8390178b2fc","datavalue":{"value":{"amount":"+0.7924630641937256","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":"Q557825$A491F878-8E27-4314-8340-BFA8B0298609","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generating bicliques of a graph in lexicographic order","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generating_bicliques_of_a_graph_in_lexicographic_order"}}}}}