{"entities":{"Q1398267":{"pageid":1409007,"ns":120,"title":"Item:Q1398267","lastrevid":43082118,"modified":"2025-07-21T07:57:28Z","type":"item","id":"Q1398267","labels":{"en":{"language":"en","value":"The recognition problem for line bigraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1956042"}},"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":"Q1398267$875B15A2-41E7-4729-9E85-7D6639C5B8E2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8379945985937feba8008437df57d20b5ca13e4a","datavalue":{"value":{"text":"The recognition problem for line bigraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1398267$F714C2B1-A8B2-408C-89C2-0437627AF605","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"33df57c006079a6f9a87fd47b436b52d4855fc32","datavalue":{"value":"1019.05048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1398267$F8293F82-33AA-4FB1-A339-2F62BABABFFC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"110eee7b346639e62b61d56516e3962d4fc92205","datavalue":{"value":"10.1016/S0012-365X(02)00691-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1398267$0514F588-896B-4BC8-BADD-9E521B3C01FF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eff762197dd54e00deaa160ce0bb6a3d51702cd3","datavalue":{"value":{"entity-type":"item","numeric-id":178604,"id":"Q178604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1398267$0FD7A172-83B2-41A5-BA6E-4CE4F5B22100","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1398267$C431C8FE-BC9B-4257-92E2-51A5F41C7EE9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bb93fa1c465ad8bc2fa283bb0b87b8516d9e8f76","datavalue":{"value":{"time":"+2003-07-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1398267$78D41F28-011D-4BA8-B942-9E5121ECD19D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"60dba95a1bcf162705da6170ee48678d38461fb7","datavalue":{"value":"The line bigraph \\(G=(E_1^\\prime, E_2^\\prime,F)\\) of two graphs \\(H_i=(V,E_i)\\), \\(i=1,2\\), has disjoint copies \\(E_i^\\prime\\) of \\(E_i\\) as partite sets, and \\(\\{e_1',e_2'\\} \\in F\\) if \\(e_1 \\in E_1\\) and \\(e_2 \\in E_2\\) share an endpoint in \\(V\\). It is NP-complete to decide whether a given bipartite graph \\(G\\) is the line bigraph of suitable graphs \\(H_1\\) and \\(H_2\\). This problem becomes solvable in polynomial time if \\(G\\) is \\(C_4\\)-free or \\(\\delta(H_i) \\geq 3\\) for \\(i=1,2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1398267$A76F3D19-7708-45B6-B80D-2732C25CEEAB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1398267$B367A0F2-C53D-48A3-BC5B-C60B914CABAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1398267$41815D29-37FF-4FA4-826E-08ED91E8FC07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1398267$4E617C31-94AA-455F-8982-028B9A479735","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"afd1dfdedb740e1b8d90f35a65df47ee94242d36","datavalue":{"value":"1956042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1398267$97DB8702-8798-449F-BBDD-893B2DCEAD30","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ebf47ee9d46796d88ef294ea48c29cd5b695e08","datavalue":{"value":"intersection bigraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1398267$B849501B-5408-491E-A7D9-77668595AEED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"57bdff1a54d6186f38add0353d489d300f224f59","datavalue":{"value":"line bigraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1398267$BBBE37AA-423F-4ACA-AC1E-7B20D295E15F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2640b3f41a7aa570a8f30372d87da740cc5e9d31","datavalue":{"value":"biclique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1398267$5F9FC1C3-A6B9-46FD-9CE2-833BF2B54AA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9891227b3d7ca9f091fdc17473271d45c5e2f962","datavalue":{"value":"recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1398267$BE96D3C9-BC4D-4F2C-8C45-FF008E88623D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1398267$182E18E2-C241-4FC0-A5C5-6DD1FD82D383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1398267$D642ED36-A6CF-4128-AEFF-7CB22E92B27A","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":"Q1398267$B36E208C-3589-4D75-A232-BC9A6E18304C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7df24f9eafc849986a24d5af93caa9bd0f02e95c","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(02)00691-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1398267$08DAC5CD-D29D-4411-8210-8925F9DE8844","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ba8e4f585e817cd0b39948fa238bef3abbee2556","datavalue":{"value":"W2009514040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1398267$51E0AD2B-54D1-478A-B27E-B102111231E6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79bf5f6ce8eb9a3eb93353cbb1f75e605fa67e63","datavalue":{"value":{"entity-type":"item","numeric-id":3694709,"id":"Q3694709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19d4680019349e9967b6f120be2dcbcd4908152c","datavalue":{"value":{"amount":"+0.8884031","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1398267$520FBCE7-C11A-4A02-B6E0-4793A0A29F1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f3430e84a836dd17d678d2f8ba7d7cd1d31c535","datavalue":{"value":{"entity-type":"item","numeric-id":4575657,"id":"Q4575657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a42e5faef03b858bd0f156dbcfe13a8151560e3e","datavalue":{"value":{"amount":"+0.88620937","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1398267$DE8FEE0E-26C0-4645-95AE-F6D66DB142B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"903221e511a89b88a16e4ee841e534da6835b7f0","datavalue":{"value":{"entity-type":"item","numeric-id":442382,"id":"Q442382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b65b34a55de721e567406fd6a718159429b82ff9","datavalue":{"value":{"amount":"+0.88055265","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1398267$FABAA46F-AE52-4AB4-996B-63980DDEBC3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5137707c908952291750748b9361dc634289d0f","datavalue":{"value":{"entity-type":"item","numeric-id":1331889,"id":"Q1331889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4813b90887c1cb6bbb48df76820c058b60aa764","datavalue":{"value":{"amount":"+0.87652504","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1398267$6A4F9C85-D605-4B9B-85ED-CA7F8AC001FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a373b96adb9199e53b77e7e88d7943f4dfc4ab4","datavalue":{"value":{"entity-type":"item","numeric-id":1765379,"id":"Q1765379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02f177ec0961a8f190d5a8f3798d2ff07d9de667","datavalue":{"value":{"amount":"+0.8718265","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1398267$D789054E-A9C5-4F40-B9C9-1CAAB529A1BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"318ee3017cab860d45e145e6902b16a61d6371a0","datavalue":{"value":{"entity-type":"item","numeric-id":3115177,"id":"Q3115177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e033ae3553e086d085cfb396be0984491d69fea","datavalue":{"value":{"amount":"+0.87165266","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1398267$5B347F4C-2FC7-4AF6-ACBE-5C3B8676EA23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"415ef28249cc555031dd2a72553fd043615b0c34","datavalue":{"value":{"entity-type":"item","numeric-id":888591,"id":"Q888591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f490c4d94882770abd68cf195042a7195e440aed","datavalue":{"value":{"amount":"+0.86995995","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1398267$6D305AE8-98DB-4FB4-A1CC-135C5648D4E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"819c3b775bbe789ceffe91ddf2952aa4aa4735e6","datavalue":{"value":{"entity-type":"item","numeric-id":1924495,"id":"Q1924495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56046d235cc82c45f9132701a3644b175b896353","datavalue":{"value":{"amount":"+0.8635584","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1398267$F59B1CE5-02A8-4F5C-8864-57755FAF08D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ad5da996694a949d90518dc8e7cfe887db888ba","datavalue":{"value":{"entity-type":"item","numeric-id":3225119,"id":"Q3225119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a944403d6b23524a8bd53d33d19d66d64c8d4a4f","datavalue":{"value":{"amount":"+0.8615163","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1398267$FC349479-C0FB-482A-8FFF-28D017AEF448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c255f38a714f1213300fe8a7260d70b4a73dd669","datavalue":{"value":{"entity-type":"item","numeric-id":1868840,"id":"Q1868840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3840d97e41cc2c1c2e426f8752ce19e63b823891","datavalue":{"value":{"amount":"+0.86068213","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1398267$D6390899-5821-45D5-B3AC-C3EC846BAE90","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1398267","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1398267"}}}}}