{"entities":{"Q1297428":{"pageid":1308178,"ns":120,"title":"Item:Q1297428","lastrevid":70091445,"modified":"2026-04-13T12:23:04Z","type":"item","id":"Q1297428","labels":{"en":{"language":"en","value":"Balanced cycles and holes in bipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1321789"}},"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":"Q1297428$665CB6DE-8D73-4701-9314-2BFE2B555AEE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"df6de18cc2d18050b85bcf8d25e601785cca74e9","datavalue":{"value":{"text":"Balanced cycles and holes in bipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1297428$F164B607-6E41-45E8-BF16-DD941B66ECFB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b33bec4759853f3ae51f85c8fb8d1ed1bd7f8a16","datavalue":{"value":"0939.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297428$DD14E50F-573E-41C5-BFC6-94ACA74DD218","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a24f4a9db9b2f348b66edc3677cb83a8948e5b1a","datavalue":{"value":"10.1016/S0012-365X(98)00283-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297428$49972C2F-1AC5-416A-A88B-BC342DC27DE1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa9a170b566faa650496c61eaa134019d05c6a23","datavalue":{"value":{"entity-type":"item","numeric-id":203960,"id":"Q203960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297428$49B620E3-33B4-4C4A-8EB6-766F709621AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"49d526c3d79304181fc7ca4f0d651cb2855460b7","datavalue":{"value":{"entity-type":"item","numeric-id":203962,"id":"Q203962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297428$153CC285-6A57-4615-8C90-B280D88D1F03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"feb07495fa8de76912d587852b3aa20404b344f1","datavalue":{"value":{"entity-type":"item","numeric-id":163019,"id":"Q163019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297428$B780F875-DC39-40E5-9B9E-A6DB0362C50E","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":"Q1297428$DD227BEE-F00E-4DCA-A264-068E1AB1E149","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9be5ba67ef43776cb1ea5c3063837b367d1caf4b","datavalue":{"value":{"time":"+2000-07-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1297428$79B63C2F-1ED6-4405-B30B-08E370B35EA4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e86e70d4be6e37b727494e1ba16ceaba058beb43","datavalue":{"value":"The authors show that the following two problems are equivalent for a bipartite graph \\(G\\) where each edge has been assigned a weight \\(+1\\) or \\(-1\\): (1) Determine whether \\(G\\) contains a cycle whose weight is divisible by 4. (2) Determine whether \\(G\\) contains a chordless cycle whose weight is divisible by 4.   They describe a linear algorithm to decide whether a given signed (edges weighted \\(+1\\) or \\(-1\\)) bipartite graph contains a chordless cycle whose weight is divisible by 4. Finally it is shown how to decide whether it is possible to assign weights \\(+1\\), \\(-1\\) to each edge of a bipartite graph so that the above properties hold.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297428$4AB38506-26DB-45D3-8FFF-25AF79F4CEB8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297428$AD85AB35-E9C0-4419-80E5-F45B06EDFE5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b2773d305bb22ed635d748bc939993c6750608ab","datavalue":{"value":"05C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297428$317E0D45-E486-4055-BBC8-C51AB18F38A7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9f19b4a559109c2a5e53caf338784def23f6f70d","datavalue":{"value":"1321789","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297428$08759C4E-AB81-4BFB-BB37-66152B2CD08D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f7c713001b6ae067de075dc4b8ffb48f907aa82","datavalue":{"value":"signed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297428$9113ACC8-933C-490B-B1C4-D600F9F2D41C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297428$70B34FB4-442E-4226-929C-01375DCDB9A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f88036c3e3561f9f0c7a56cd24c12ac688b07e2","datavalue":{"value":"chordless cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297428$6FDD7338-0537-4D27-98A0-E76D013EB59C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a49464e2d7be3b5ec6afa9a7b997ccf87f3adaab","datavalue":{"value":"linear algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297428$05F36552-C218-4AF9-B4B9-529FE1783EEF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eee744981d92ac19b8d353f3a45a83ebd916fb73","datavalue":{"value":{"entity-type":"item","numeric-id":558237,"id":"Q558237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297428$21D09F19-4A53-4CAE-AD2B-71AD75CD61EB","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":"Q1297428$CE0516AA-B98B-4B56-8375-CB7AC6BD13E5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"85cfa63f67ed3743ed6d983c37c02f4185c5f671","datavalue":{"value":{"entity-type":"item","numeric-id":5811782,"id":"Q5811782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297428$1CB7B72A-F49B-473B-B064-54753A2D4E28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1257f9c1023a29b8b0b6fc9d388c15555f3bf18","datavalue":{"value":{"entity-type":"item","numeric-id":3924253,"id":"Q3924253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297428$F290579C-DE83-4424-913B-803DE3FB38F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e93fcc5f5e8911813f16fcd1e3e08e519d9e013","datavalue":{"value":{"entity-type":"item","numeric-id":4767335,"id":"Q4767335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297428$B63F86A6-706E-4D2B-8AC4-39D28807B5B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67892797163ff58ab82ce3096e6b7427afe0ba57","datavalue":{"value":{"entity-type":"item","numeric-id":1160629,"id":"Q1160629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297428$7E2DBD8D-3777-4C2D-8D4A-26A449337210","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28f6f4dd626c0576205b38129f040264bfa162ef","datavalue":{"value":{"entity-type":"item","numeric-id":4004142,"id":"Q4004142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297428$97D6F9D7-0E3E-4789-8C90-945562B25121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8dfff1846e7e39c81f69451d2c8f09c9aca2db6","datavalue":{"value":{"entity-type":"item","numeric-id":3781793,"id":"Q3781793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297428$792422A3-9D53-4EF3-8368-67EAB747AF40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b084fd23a4e64f5f3680a8f9c0c45f2c9f039cfb","datavalue":{"value":{"entity-type":"item","numeric-id":3680604,"id":"Q3680604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297428$E1F76AAC-0071-4AE4-BFC6-E2B2292B5995","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"ba7d88a95b7ac638e5fe56a48862571a0da69fb9","datavalue":{"value":"Q126472657","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297428$01D3795D-46BB-4857-BA79-AF9FBD1D1E62","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"636b5596a03bf39ac01a9edec8e66115d131e66f","datavalue":{"value":{"entity-type":"item","numeric-id":4298853,"id":"Q4298853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4f006ef5d03bffb68221e3ffd66e4af9a575288","datavalue":{"value":{"amount":"+0.7859745621681213","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":"Q1297428$28E9047A-1F21-4555-9B80-822915972DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1b0d1c0ffa135878ab6659a4646b3bc49f3be88","datavalue":{"value":{"entity-type":"item","numeric-id":1823869,"id":"Q1823869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af333b574fcf978831e9f676d124d53a805369ee","datavalue":{"value":{"amount":"+0.7837429642677307","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":"Q1297428$B9964B18-A782-4633-B58C-300426C4B43D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2715ca854a3a2a69d238306cf75453ddf678f126","datavalue":{"value":{"entity-type":"item","numeric-id":5319255,"id":"Q5319255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bf96b7e5ccce2a35d0a90b8e5f9b0f24c914388","datavalue":{"value":{"amount":"+0.763645589351654","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":"Q1297428$0282E06C-BE78-4E54-B909-B06A2AB1EB2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"202fb0edc83fab8fccbe6b254aa731f02dc2f6b3","datavalue":{"value":{"entity-type":"item","numeric-id":3633844,"id":"Q3633844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75f49f8d60fceb03b02a6d4504def88a2d6abeb6","datavalue":{"value":{"amount":"+0.7545081973075867","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":"Q1297428$10DC21BC-CAE9-403C-894F-F3CEFE50350A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d85e1d3e56394112652bd409c98a9e1b3e6b7ed","datavalue":{"value":{"entity-type":"item","numeric-id":5272932,"id":"Q5272932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b474d0f1683fdebacf6394276d3ca29956ae6cb","datavalue":{"value":{"amount":"+0.7510372400283813","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":"Q1297428$8359ABE5-7740-4EFE-8886-079F2D3A23E4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Balanced cycles and holes in bipartite graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Balanced_cycles_and_holes_in_bipartite_graphs"}}}}}