{"entities":{"Q1736638":{"pageid":1747379,"ns":120,"title":"Item:Q1736638","lastrevid":57516393,"modified":"2026-03-31T05:59:56Z","type":"item","id":"Q1736638","labels":{"en":{"language":"en","value":"Recognition of unipolar and generalised split graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042236"}},"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":"Q1736638$D6BDD3F4-D4A2-4AE4-B718-00E2D5EA4B0B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6007903238ef1a8040a18d4cf67e5fdcf40c1994","datavalue":{"value":{"text":"Recognition of unipolar and generalised split graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736638$18CCB935-77F2-4F1A-AF92-551EAC1F0239","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"00b776ed425b657f11237b3a2fda175f0e5c6b6d","datavalue":{"value":"1461.05216","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736638$C97E5F7D-A2E1-4482-A6A3-1369F80977DF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a5f347a11acbb271b9c1dc66d1c73e7323aa44b6","datavalue":{"value":{"entity-type":"item","numeric-id":1637140,"id":"Q1637140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736638$979AFEBA-A2A4-47C9-902D-CE64A4ED9AB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"03f08a3cbc69e48052a97dab7b19fd1cbcee9fe9","datavalue":{"value":{"entity-type":"item","numeric-id":1227010,"id":"Q1227010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736638$BC75E6BD-F94A-4514-8252-171510E39D8C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736638$AD39FDEE-33B1-44FF-A3C5-7E1F09512A61","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736638$2E18C960-7A04-4322-92AE-5EA01AA603F7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3778cb61785ca33f24bb3210cedb46cb4e249aab","datavalue":{"value":"https://arxiv.org/abs/1604.00922","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736638$84127CDD-B0B8-4888-BEC2-4773B8459B6C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6572380c5b1f2ce6e147d440ef759a838cdeca01","datavalue":{"value":"Summary: A graph is unipolar if it can be partitioned into a clique and a disjoint union of cliques, and a graph is a generalised split graph if it or its complement is unipolar. A unipolar partition of a graph can be used to find efficiently the clique number, the stability number, the chromatic number, and to solve other problems that are hard for general graphs. We present an \\(O(n^2)\\)-time algorithm for recognition of \\(n\\)-vertex generalised split graphs, improving on previous \\(O(n^3)\\)-time algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736638$D8D3B811-59A3-4E0B-9E2B-2109BDA411B8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736638$E2DDEFC4-6B83-45E8-A88F-F8124B26D7D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736638$F1FC7F87-0C4E-4220-A392-B581BB239D0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736638$87081D65-3B0A-4062-A72C-6CEDD236BA03","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"34cba264b67a57c63c4a5019276fefc40f775487","datavalue":{"value":"7042236","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736638$C1398148-A9D1-4A16-899B-B172A6BA2340","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cde8fc2cbcefc2aa3edea76f75eb71a9140fe020","datavalue":{"value":"unipolar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736638$C7BD4C3C-795C-4DB1-BEA1-48DECE1845D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e289cfe64506819ab9090150a50ee5d568d44840","datavalue":{"value":"generalised split graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736638$9E1405A0-86A8-40EA-9ADD-AB81B21FBB83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736638$EEEB238C-DF4B-4D2D-9AB5-803C4C3320B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8de0f0c5e02cd0505a6f3655182209c90c31101a","datavalue":{"value":"recognition algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736638$E0541B50-0ADD-40BF-BD2F-66C5FF8A3E40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1faf8468e79a01663beec97348aa6b18da393113","datavalue":{"value":"representations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736638$58CCE50C-4920-48CB-AADD-D00FE76DF24C","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":"Q1736638$8418BEA3-E723-46F5-A9B2-0A73E544CAE0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a7f4c66a9354cf003d17c9fbdeaf15cccc57042c","datavalue":{"value":"W1973229660","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736638$9E690EC9-8321-4F95-9AD2-784E0FAD2EBC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f364dc4fd504177d7b1dd81b80d2ec7f5f036f6c","datavalue":{"value":{"entity-type":"item","numeric-id":4291185,"id":"Q4291185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736638$3E354A11-8CAF-42FC-B716-57BD6051716D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20e0b8b69bb74bc107c5a48305e78f34c64cd1d","datavalue":{"value":{"entity-type":"item","numeric-id":2494439,"id":"Q2494439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736638$72D41023-6D5E-4E1A-BBB2-E464EFDB3604","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70932f1cf740819121b6dff2db80775f668b9c68","datavalue":{"value":{"entity-type":"item","numeric-id":3216686,"id":"Q3216686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736638$44F89812-62AB-4729-A677-A0C9EF2BDD85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c84149f4b486631b0957b9c1a37299214b49c9ad","datavalue":{"value":{"entity-type":"item","numeric-id":741738,"id":"Q741738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736638$13BD4DB1-4D55-42DF-ADB5-7F3DBE03C852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6619826e480ae1ba64e56a53850ec42b5b121be9","datavalue":{"value":{"entity-type":"item","numeric-id":3743346,"id":"Q3743346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736638$C602CCE9-BA9C-4AA4-AAF9-FBB7EEBC8C58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff4aee7832c32a24c9a612a770dbb7d5c08d2d17","datavalue":{"value":{"entity-type":"item","numeric-id":742575,"id":"Q742575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736638$65BCCCFA-3C81-4BF9-852F-A4A20B4C0C37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736638$90C80087-DDF3-469B-942E-BA7F609E8B04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf035d2fecb7e445991dd16e141f37bab3768a8","datavalue":{"value":{"entity-type":"item","numeric-id":1254112,"id":"Q1254112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736638$5885E72D-DFFF-4EB7-8B2F-77F4FAC766BB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"be07e508cf286c54fe0dabed753f716adfb9b66a","datavalue":{"value":"10.3390/A8010046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736638$1F63F36C-6F6E-4873-BDB5-F48A760C3EAA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f58c7a7327cf9da113f944ac1e18a71d88ae1179","datavalue":{"value":{"entity-type":"item","numeric-id":741738,"id":"Q741738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"adf01680ed05b0f7263c6e114a651ae4a924ce55","datavalue":{"value":{"amount":"+0.9369081258773804","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":"Q1736638$DAD7B6EC-0C7E-4A06-925B-6CB513D1A618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2a60e44b9741813aa56acadfb133d88b188680d","datavalue":{"value":{"entity-type":"item","numeric-id":5369516,"id":"Q5369516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1952b47006cabe226b8648dbe83dacc6c93549b","datavalue":{"value":{"amount":"+0.8153318166732788","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":"Q1736638$7A67E913-EB5C-4A06-AD47-B2FD23FFAE40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5fb58dca47428bd3e0b52bc66303d5f76a8171c","datavalue":{"value":{"entity-type":"item","numeric-id":5167717,"id":"Q5167717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f4f3def18c46e835e19da51e87e814af26e642f","datavalue":{"value":{"amount":"+0.8091365098953247","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":"Q1736638$82919EE6-537C-445C-B470-CD799039E4F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffe8c76080c5275385452c88d3a438b927837873","datavalue":{"value":{"entity-type":"item","numeric-id":742575,"id":"Q742575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd6b821e97bf8b8edf030dcda49ef5f6950d6ea5","datavalue":{"value":{"amount":"+0.806304931640625","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":"Q1736638$7F3D8DCC-12C0-41BA-88B4-14C544308A7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7a28a35597c61a92f90bfb2c33043f47bdf53f9","datavalue":{"value":{"entity-type":"item","numeric-id":5900347,"id":"Q5900347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"881e01f2f5979f8fdea8a9b373364ff1dfa1a211","datavalue":{"value":{"amount":"+0.8001686930656433","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":"Q1736638$FB14EFDD-4B4A-4DC0-A999-79080E7C4679","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736638$619CF507-A1B0-4815-B0EA-71347FDDAEE9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736638","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736638"}}}}}