{"entities":{"Q1302156":{"pageid":1312906,"ns":120,"title":"Item:Q1302156","lastrevid":70101141,"modified":"2026-04-13T12:27:01Z","type":"item","id":"Q1302156","labels":{"en":{"language":"en","value":"On the extension of bipartite to parity graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1340635"}},"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":"Q1302156$97827418-DA01-404F-A282-23A26A1FA725","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6690fdaab4efe47df7b30ba88c6bbafa288c9e4a","datavalue":{"value":{"text":"On the extension of bipartite to parity graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1302156$2710D3F7-6864-4D2C-9223-EA47833CD0F9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3aa88bed8086d8a1cc9037cc08c86ca1b17abf3d","datavalue":{"value":"0933.05132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302156$6B0BC074-9330-4B3A-90C7-13F679EBEA99","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ec98af808f480ccfb2b0a423208f7941166ed85d","datavalue":{"value":"10.1016/S0166-218X(99)00074-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302156$170E31DB-9D97-4F65-A15F-BC0CE6B3353F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5254501b18649e16eeebf46a3730e555a1f783b4","datavalue":{"value":{"entity-type":"item","numeric-id":169276,"id":"Q169276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1302156$F16877A7-B42E-4740-848A-78D48B6CFA85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dde09a0944e88be3f96603714bb742e988212805","datavalue":{"value":{"entity-type":"item","numeric-id":169277,"id":"Q169277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1302156$3CCC995F-B09D-4990-821D-A9803A2C583D","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":"Q1302156$EC2CE15A-0306-45D6-AC11-F403BD59E51F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"133f6ae6dfb800b668c32271be33f0f9ba6e88cf","datavalue":{"value":{"time":"+2000-04-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1302156$7676CF6F-D619-4363-8579-BCF3B2794B74","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"204ef64496ca09ab6e55749d0beceb7d6bb86d9f","datavalue":{"value":"A path \\(x_0x_1x_2\\dots x_k\\) of a graph \\(G\\) is induced if \\(G\\langle\\{x_0,x_1,x_2,\\dots, x_k\\}\\rangle\\) has \\(k\\) edges. A graph \\(G\\) is a parity graph if, for every pair \\((x,y)\\) of vertices in \\(G\\), the lengths of induced \\((x,y)\\)-paths are of the same parity. Clearly, all bipartite graphs are parity graphs, so are distance-hereditary graphs. Using the split decomposition of Cunningham, the authors show that the recognition problem and the maximum weight clique problem for parity graphs can be solved in linear time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302156$D6AA6A2B-74AC-40C6-A789-F2A0E86C7993","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302156$68F067C6-7599-4608-981D-A0AC9B601961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302156$6E355756-1AA8-4A38-83AE-D61DC3FB0B7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302156$90D39D8C-F239-4D4B-B7D6-E915D6276FC0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3b0d2264a1a110458e5b86e3a866fda7b50478fa","datavalue":{"value":"1340635","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302156$BB6A7E2D-A3A8-4D97-A799-11163651812D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25832dfa9e21272dfcd1a25394016e65412503ca","datavalue":{"value":"parity graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302156$1260ABB4-401F-4B8E-84BE-12915BB1035F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eecb173004633ca38efc326bcd073800d8b745c9","datavalue":{"value":"bipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302156$885DA98C-E73E-4672-9A40-64479A6B5F34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb3f1aa9121d6bf85273adec97cc9f7670b5ff2e","datavalue":{"value":"distance-hereditary graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302156$3F9044C3-927D-42CD-B0A0-BB51C95EF7B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dde62c1d9c84b346656546e8881b2406b933d488","datavalue":{"value":"split decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302156$3DBC0E17-900B-4118-BD86-317DD62CC800","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4fefa17be9d4bfc1a51cd1d93e86e23724d8c0a1","datavalue":{"value":{"entity-type":"item","numeric-id":168084,"id":"Q168084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1302156$DB2CDCBC-CCF7-4639-AFCF-669652BDB22A","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":"Q1302156$97AA90D0-B92D-4F38-9851-76FABB474DD2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee396aafba50c530fd089384ca3538b4587f05b4","datavalue":{"value":{"entity-type":"item","numeric-id":3222874,"id":"Q3222874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6050df9226df0fb8171482df8bb42887f814901","datavalue":{"value":{"amount":"+0.8569353818893433","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":"Q1302156$42DA3926-CB8D-4DEC-A75C-CDBBEFCD7A40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c253d2b3460142f8e8e0b3cf2a0695ce85ab6db","datavalue":{"value":{"entity-type":"item","numeric-id":5851119,"id":"Q5851119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8295b7fa9f04ce7a6009c9e3f7722b1c91764059","datavalue":{"value":{"amount":"+0.8139054775238037","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":"Q1302156$DB0F0E79-A2CF-4E45-998D-477135C2D7C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a72362f339ca91d66b0ca1007e54b7d37f42590b","datavalue":{"value":{"entity-type":"item","numeric-id":2428656,"id":"Q2428656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05230284a84f4d02c74b78ea2e306baab64fe57a","datavalue":{"value":{"amount":"+0.8112559914588928","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":"Q1302156$6C39B300-8EC2-4D4D-B638-D866500ED899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96d532e7238e9e978f32044287e9dc35f6d525ba","datavalue":{"value":{"entity-type":"item","numeric-id":3201757,"id":"Q3201757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59c0a9bc1b362a200a6da9990aed7a3a424df446","datavalue":{"value":{"amount":"+0.8028567433357239","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":"Q1302156$8EDD94CB-F394-43C9-B6A6-C626771F6315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4984d015baa3c1dcd210da71544f2428422c96df","datavalue":{"value":{"entity-type":"item","numeric-id":1182856,"id":"Q1182856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db8c70dbdc1c40b9ae845ad27b584b2b4152c4ad","datavalue":{"value":{"amount":"+0.7994401454925537","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":"Q1302156$0009771B-5E07-4D22-ABD7-D08E75356981","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the extension of bipartite to parity graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_extension_of_bipartite_to_parity_graphs"}}}}}