{"entities":{"Q1092931":{"pageid":1103683,"ns":120,"title":"Item:Q1092931","lastrevid":49102072,"modified":"2026-01-06T14:39:05Z","type":"item","id":"Q1092931","labels":{"en":{"language":"en","value":"Bipartite permutation graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4021195"}},"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":"Q1092931$FF6F2A00-1DDD-4FC6-B845-916BE49849CE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"984f6f5e8fee72d96cce55759e8dd66cfb1645b9","datavalue":{"value":{"text":"Bipartite permutation graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1092931$56FA9BC0-262B-4A80-8A73-9FB68F524F87","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8b20ec9120cc7cf70ca4744b7e0a1688971616eb","datavalue":{"value":"0628.05055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092931$D2B3E98A-7351-4AD3-AC3A-2DF554CE3792","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"573fed0e30a5734893b34f48936d00f0beadb78d","datavalue":{"value":"10.1016/S0166-218X(87)80003-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092931$B04F98B9-5376-4F5A-AEBA-F7BD69F7F0C8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbb68d9de22321af7fb543db220c0a16a741857c","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$0AD2E7F2-AFB2-4B4A-BB51-F42BC1480C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8fb2b37962e8c2e7db338cb8271d20e81b4c70da","datavalue":{"value":{"entity-type":"item","numeric-id":1060965,"id":"Q1060965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$EAB60CB1-7F85-4FC2-9911-819A8350D905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ef8392e01c11e85b032ddf62d87088b822bd19a","datavalue":{"value":{"entity-type":"item","numeric-id":344852,"id":"Q344852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$C901B7E4-B8DA-470F-AD05-081899539252","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":"Q1092931$4F4BE432-7592-4048-AAE6-B538D868DA54","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1092931$B85FB234-4A59-4BAB-B1A0-F604B1016573","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c1fe2d64795e6ed826108a173147ed01e032b5a3","datavalue":{"value":"It is shown that bipartite permutation graphs have good algorithmic properties in contrast to general bipartite or permutation graphs. Two characterizations of these graphs are presented which lead to a linear time recognition algorithm and also to polynomial algorithms for Hamiltonian problems, a variant of the crossing number problem and the minimum fill-in problem on these graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1092931$F9C09EE1-6E61-42A3-B128-DAE5C69BACED","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"28b1fb367b3a6335e647ddbd540f63d134723dd1","datavalue":{"value":{"entity-type":"item","numeric-id":222481,"id":"Q222481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$B5CE2376-3D61-4920-8EB6-753CFDA440F3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092931$00C7B5A3-5128-4125-8835-5927C36904DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092931$49A4E066-1C69-4AE4-B486-1C7100744099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092931$27E6151F-4DC9-4BE9-8F38-07A7C11D3B65","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ac2efe7d60daa1d384af22975e58115ec47083e4","datavalue":{"value":"4021195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1092931$99925822-A686-45B3-B3DF-D31F1BB499B1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1092931$AAEAE032-28D2-448B-AF87-CD5E0CC390A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1092931$0222A840-693B-4D50-8123-A28C83BDE61B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"972b47051b12a25f42ccd0a9702464009e0dcd44","datavalue":{"value":"permutation graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1092931$61FBFBEE-91A0-4F3F-A5E5-9782CB53781D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0bf0dbd5dd844463866c53b1b3f022210f94a95","datavalue":{"value":"crossing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1092931$6AF6BBCF-465E-4CFA-98CA-4B37E848D900","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":"Q1092931$2AE66920-66F1-4C9B-90F7-6BF04E26007D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"db695381606ba322df78c7a9c05e7660a22ed7b4","datavalue":{"value":{"entity-type":"item","numeric-id":3888545,"id":"Q3888545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$4916DCFE-20BB-47EF-8F25-B7FFAA5408C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"854b218c601f0ae7cfd0cc5e37fd735c66fa3670","datavalue":{"value":{"entity-type":"item","numeric-id":3679238,"id":"Q3679238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$A1697DC0-EB2D-425D-988E-EF975C7DBA0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f756c07ac6477382de77f3815b2ee68efe79e0c","datavalue":{"value":{"entity-type":"item","numeric-id":3715153,"id":"Q3715153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$0B1ADF61-0F48-4B65-A547-E928E5588C7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9914f8121a32baf6895c6797ec99c63c32102968","datavalue":{"value":{"entity-type":"item","numeric-id":1242450,"id":"Q1242450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$9EFA3FE1-8416-4891-8E7E-58D92E7DD2E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$A1CB2F48-8079-43F7-AE2A-9DDB50F1362E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"224ad1a17328eb20bf4beee8188b5c55558e4ea5","datavalue":{"value":{"entity-type":"item","numeric-id":1060966,"id":"Q1060966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$7D99B064-1A68-48C9-A9A8-E887B44D2D50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7df60897b7f36fcb755315945b431813c52a78e4","datavalue":{"value":{"entity-type":"item","numeric-id":3910010,"id":"Q3910010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$5A621C6F-51E6-4E5A-A79F-590038F29F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"319fdaa27484a2ebcce1969d012e31307e954320","datavalue":{"value":{"entity-type":"item","numeric-id":5663894,"id":"Q5663894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$9ED4A2F1-0CAD-4E60-8C18-A426549034C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1901aedd2d8549517a3f77a27b2a3787fa019529","datavalue":{"value":{"entity-type":"item","numeric-id":3731637,"id":"Q3731637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$E516EFB0-014A-4DC1-88B9-46F38E62C190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8539d1fcf3cff5fbb08dd6973662b887ad57892","datavalue":{"value":{"entity-type":"item","numeric-id":5534028,"id":"Q5534028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$02F37428-0311-438E-8838-0E961E21510E","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":"Q1092931$FEC1E74B-B7AE-4D4B-8D80-51CFC7A72ACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c17b1143dff0bc685088f8d62dbc046a1f96e02e","datavalue":{"value":{"entity-type":"item","numeric-id":5732670,"id":"Q5732670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$2D24619E-DC6C-4721-A173-A3BA44BEC434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e68a7efc10f8e8ea4e36f7d70001059b8c12d905","datavalue":{"value":{"entity-type":"item","numeric-id":1241524,"id":"Q1241524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$631F73DC-0BAD-4754-A856-93C9C534F383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$D83A0981-B064-4BAB-BC65-AEB68C346DDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$70E5A262-38BC-4777-9F95-1C2A56B3C99C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fa97f0110ceefce3316c5fbe9c21778948ad688","datavalue":{"value":{"entity-type":"item","numeric-id":4742820,"id":"Q4742820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$7F421D92-7F14-487C-9E4A-CDAAB213F045","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"842b1f582c7be954c64d94d41d773a79c4d9a96e","datavalue":{"value":{"entity-type":"item","numeric-id":5905223,"id":"Q5905223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$89BCD143-F530-440E-BF5E-D16063A94753","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f3a345ac969991571213b2a34fe3bc06c137d18","datavalue":{"value":{"entity-type":"item","numeric-id":5896404,"id":"Q5896404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$913D8667-D10C-4FE7-82D7-DCFC20CB9F2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0285625f074a48cd1908122f2f7d851fdd299e","datavalue":{"value":{"entity-type":"item","numeric-id":3747723,"id":"Q3747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$44B91A1E-36D6-4884-B20E-2E473703E938","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c9a77b50c698d35e0bfbd498c866f480eb9f390","datavalue":{"value":{"entity-type":"item","numeric-id":5591387,"id":"Q5591387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$423D6A3F-6926-426F-8883-4E5BDC3E9600","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cd900a9928338cdadd8e18c47b33b430f9560c7","datavalue":{"value":{"entity-type":"item","numeric-id":5602691,"id":"Q5602691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$23C041C6-A24A-40A1-BC9B-30763A6BFE8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a3f4f623c55f4103180bc7ed3e80e030c1afd8b","datavalue":{"value":{"entity-type":"item","numeric-id":2545884,"id":"Q2545884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$F7EBA67F-945E-47D4-851C-A27DB2F94CC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"565e1c631f28f5626e28b4b72f070c887ee0b094","datavalue":{"value":{"entity-type":"item","numeric-id":3685215,"id":"Q3685215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$E8A6E02D-ED10-4C23-BBF2-686547DAB0ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45bf10a9f666727577e0ebdf94e82c9ce3bd7c24","datavalue":{"value":{"entity-type":"item","numeric-id":1090688,"id":"Q1090688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$621A8204-0B37-4DED-BB0F-25DC4ED7F4E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20b9c062c65fa50baeb0cadac82aad397e032bf","datavalue":{"value":{"entity-type":"item","numeric-id":3960122,"id":"Q3960122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1092931$5E633105-D43F-4CD4-B75C-B01E7CF81D69","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d39139727e3fe1503b644b70c175a0169126997f","datavalue":{"value":{"entity-type":"item","numeric-id":4390698,"id":"Q4390698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e01f546113aef2db2a18b5b718f3421d1e6fe8b","datavalue":{"value":{"amount":"+0.8824018239974976","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":"Q1092931$EC5E10A1-891B-4517-8513-27651A534ED6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79ebadc263b95189b2ee9271db33f3b2b56fff72","datavalue":{"value":{"entity-type":"item","numeric-id":5463359,"id":"Q5463359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e01f546113aef2db2a18b5b718f3421d1e6fe8b","datavalue":{"value":{"amount":"+0.8824018239974976","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":"Q1092931$EA85C628-87A6-4A59-8BBE-12D6915D794F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a02455b174da99ec5d01677bf1046ae9de29afa","datavalue":{"value":{"entity-type":"item","numeric-id":678867,"id":"Q678867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40ec4e1ff642fade77cf70ca89ccbaa37b2bacb4","datavalue":{"value":{"amount":"+0.8457779288291931","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":"Q1092931$546B5F9A-EC00-4D30-B535-00F270440210","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfaa7f7fcbd233c1f5c3917d35c01507c4d179e3","datavalue":{"value":{"entity-type":"item","numeric-id":5285476,"id":"Q5285476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cced15405003653853542c60a182c863695f2cae","datavalue":{"value":{"amount":"+0.8370065689086914","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":"Q1092931$E107CDBD-79C8-441B-BD93-E0F8D159DF2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc77cfe7e35cfec97bc169a690803774b289f3b0","datavalue":{"value":{"entity-type":"item","numeric-id":688258,"id":"Q688258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cced15405003653853542c60a182c863695f2cae","datavalue":{"value":{"amount":"+0.8370065689086914","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":"Q1092931$98439237-E8B9-48AE-9EDC-FAA99B1703C1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1092931","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1092931"}}}}}