{"entities":{"Q911300":{"pageid":913148,"ns":120,"title":"Item:Q911300","lastrevid":49366654,"modified":"2026-01-07T01:12:19Z","type":"item","id":"Q911300","labels":{"en":{"language":"en","value":"Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4141517"}},"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":"Q911300$98E13647-6215-4F3E-86B9-70CCB7F6ED04","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"20d488aae5421e1f7e8428375a0c27363ba3c119","datavalue":{"value":{"text":"Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q911300$135B26F7-4289-4FB5-9F62-EDEA56E9666C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"07d1f95e4af8ec5ef03e57ca5070d8136be7cd12","datavalue":{"value":"0696.68076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911300$A6760138-C9CC-40DA-8564-9C01A3EA8148","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"44411214788baadf39fb5afb64175f066cbffa12","datavalue":{"value":"10.1016/0166-218X(89)90053-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911300$072D2F09-9ECB-4852-BC8F-26160434110F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d60cc394e2e4fe5c30e46e2359ff881fbae889f7","datavalue":{"value":{"entity-type":"item","numeric-id":593777,"id":"Q593777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$2A7035F8-5745-4E36-AA67-3E734F5CF1D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"64789e48fd3ab0a44b5ae0aa6d85c1c024312026","datavalue":{"value":{"entity-type":"item","numeric-id":458479,"id":"Q458479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$C33D597D-D232-43E5-AD65-4182A230C6D2","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":"Q911300$0A644AAC-C852-4A31-87E9-C875711CA82D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q911300$379EF96B-EE97-42B7-9464-03851092CC77","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d2d83fb5f7a7f5e56e6984c3352d8a199fb58e6a","datavalue":{"value":"The problem of whether one can change some \\(+1\\) into -1 of a (0,1) matrix A so that the determinant of the resultant matrix equals the permanent of A is proved to be polynomial-time equivalent to the problem of determining whether a directed graph has an even length simple cycle. The problem of determining whether a graph has a Pfaffian orientation is proved to be polynomial-time equivalent to the problem whether a given orientation of a graph is Pfaffian. Both problems are actually in Co-NP. Let A be a an \\(n\\times n\\) integer matrix. The problem \\(``\\det (A)=perm(A)?''\\) is NP-hard. It is polynomial-time equivalent to the problem of even cycles if A is a (0,1) matrix.","type":"string"},"datatype":"string"},"type":"statement","id":"Q911300$F301AD93-43C5-4D29-B817-842FC837269D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911300$70170C76-4319-473D-B4EF-E7C4B8553739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911300$212AE815-DC7F-4286-AF1C-55BEC78CEEB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911300$C8E2DFCA-12AA-4FAC-A4EF-6B0B71BECBA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5f35883713e23ca3f0ced48b60a92f4891f4d526","datavalue":{"value":"15A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911300$64245273-1CE1-48D9-A1B8-E4BF660C582B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911300$F4DF3AF8-5497-4B19-BE07-3B2668125DAE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"40318ad9f8048ad4d613a1389afe6ac50ddc4189","datavalue":{"value":"4141517","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911300$812F7F07-08B2-4E7E-B03B-640DFBF6DA99","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7049b491993343a690a58a6055f9cf7bc3b64eb8","datavalue":{"value":"even cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q911300$FF42DDFA-9724-48ED-A9A5-12970999E50D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ecde75e20fea1230a086243cffda8342cc569a15","datavalue":{"value":"permanent","type":"string"},"datatype":"string"},"type":"statement","id":"Q911300$6639DBF2-723D-443C-A42F-9AF97750825B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"606b4d5b3391fae02e9bf72ac8e0dd3d9b3c5240","datavalue":{"value":"Pfaffian orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q911300$77450D26-8360-4ADC-9B7A-04573011D760","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":"Q911300$BC6B7975-9394-414D-8933-EA129F5588B8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$6FB5BA73-275D-4738-BB7F-1E4C4B3B5784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b763b01c46543b00dfbb175ee93565d7b574282d","datavalue":{"value":{"entity-type":"item","numeric-id":1123202,"id":"Q1123202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$6DB0D671-36A5-4B69-A9C1-9B414A95548A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9b712e361bbfbc97c265dcc3e2463de06c2cf58","datavalue":{"value":{"entity-type":"item","numeric-id":1103639,"id":"Q1103639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$FDCB2A54-F57D-4999-83EB-64512E52DDDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cbdd4cf597b5efaf84d98e3a02b2ec5b678a450","datavalue":{"value":{"entity-type":"item","numeric-id":5605168,"id":"Q5605168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$B37B18AD-B6AE-4D7D-8A69-BDC754135152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa5434d99603b4edd569d7d07b4e9980a4940032","datavalue":{"value":{"entity-type":"item","numeric-id":795898,"id":"Q795898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$1D501053-318D-4653-99F7-628CE578396D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed3dbdfdb20cfcfc2164fad7e8d967c7d9ab052e","datavalue":{"value":{"entity-type":"item","numeric-id":4097310,"id":"Q4097310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$B597391C-6FBC-45AA-9B6A-E975CF6A12F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"240f29a3d8326c619e96aa9d7793e2a5ce8769a4","datavalue":{"value":{"entity-type":"item","numeric-id":1112071,"id":"Q1112071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$1A473F3B-AB7A-4D51-A9CE-92DC842C4F40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$3CCE6125-33CF-4980-AE27-027ED53A9580","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3aecb51056d98414ea32583c3f47f12c23f7dc6","datavalue":{"value":{"entity-type":"item","numeric-id":3722528,"id":"Q3722528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$E15A75D5-FFC4-4A68-A63B-1EF16389A035","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b233d1263957559f060c771e665cbb471db1f578","datavalue":{"value":{"entity-type":"item","numeric-id":774932,"id":"Q774932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$495A608C-0AC7-4835-B581-83F37AA0FCF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec62482a6f1abfd15d9d0aa6d0ca02f4b7a14835","datavalue":{"value":{"entity-type":"item","numeric-id":1095658,"id":"Q1095658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$3E891982-1E09-445C-9BE9-22D58E4368DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebce56114e63ba3525f79ee27eb4d820203e7691","datavalue":{"value":{"entity-type":"item","numeric-id":1085177,"id":"Q1085177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$515ED1B0-0A90-4664-B3B6-D927C00AF851","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f0cf3e88ff57235f2ec8b417aea4ebcbb490e55","datavalue":{"value":{"entity-type":"item","numeric-id":1084409,"id":"Q1084409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$33408235-E9DB-441C-B9C0-40104B14BEBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f4b98a5b00a0f1036d9d9262980e646239da892","datavalue":{"value":{"entity-type":"item","numeric-id":1073811,"id":"Q1073811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$55788305-3AA3-4EF1-81F9-F142E70D7E9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68c516460706e34bfacf776c096f40a576fd2116","datavalue":{"value":{"entity-type":"item","numeric-id":600247,"id":"Q600247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$9AA28C0F-441F-4BA9-91A8-956AB632AA69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dfd82bed9266a9eb9ee03c49c86a8c45cb2436","datavalue":{"value":{"entity-type":"item","numeric-id":1090454,"id":"Q1090454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$307A4039-0CD0-4515-9D5A-39369F9D67FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d65e5fa96c04c984fc37232aa1378e70a7f1aba2","datavalue":{"value":{"entity-type":"item","numeric-id":1120597,"id":"Q1120597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q911300$6D619305-0A24-417E-8A90-105E8548C80D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0f58b64c6b35543413009d487867f45ff4ab60c7","datavalue":{"value":"https://doi.org/10.1016/0166-218x(89)90053-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q911300$2D79F888-AA0F-43E2-9378-4B057282ED8E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6eb945be5d303d6f05a721917d9504ca2359ba05","datavalue":{"value":"W1966874927","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q911300$A7D43FEA-F6E7-4F19-9CA4-54C1E5EB04BC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b2a6c37d3c3a794c5f47e9fc6a4015fbb005f60","datavalue":{"value":{"entity-type":"item","numeric-id":3793731,"id":"Q3793731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61d9a3f562543ec1ee49fec8f8dd883b3b743ec2","datavalue":{"value":{"amount":"+0.9309931397438048","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":"Q911300$F3E187A3-46A1-4448-BECB-8874691DF662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cbfed4fe7303b8362a137ea1b1f72c87fc03065","datavalue":{"value":{"entity-type":"item","numeric-id":4527007,"id":"Q4527007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88f04471b51943f82b7e1711a9ef27163ea42008","datavalue":{"value":{"amount":"+0.924903392791748","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":"Q911300$EA31B83F-FF97-4A70-8199-1ED0BED7FCAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"191d0598e0c49a0b5465a7fc0877d24b44604a8f","datavalue":{"value":{"entity-type":"item","numeric-id":1971908,"id":"Q1971908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32f3b9925294ada4be2fcef3dce713f2790cff64","datavalue":{"value":{"amount":"+0.8770940899848938","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":"Q911300$0499A57F-F90D-48CB-93BB-B45DFB97FDEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba717b0a6b645f7f8d360a0890f33bc35df1fea5","datavalue":{"value":{"entity-type":"item","numeric-id":1773170,"id":"Q1773170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1b6c926c348ee0e386ea9a372ed2936f8e2a9ae","datavalue":{"value":{"amount":"+0.8447695374488831","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":"Q911300$ACB67FB5-F4D1-45BF-A915-4BE96D30B706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fec5e376574c2111104ab16cecc1246f8683eb18","datavalue":{"value":{"entity-type":"item","numeric-id":5491020,"id":"Q5491020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59e0d4ff97e375df3c9b820a0e50584a76b7220c","datavalue":{"value":{"amount":"+0.8400850296020508","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":"Q911300$B64CCDFD-CA69-46BA-A514-1FE572F4B671","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:911300","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:911300"}}}}}