{"entities":{"Q1972676":{"pageid":1983418,"ns":120,"title":"Item:Q1972676","lastrevid":46903494,"modified":"2025-12-25T20:03:09Z","type":"item","id":"Q1972676","labels":{"en":{"language":"en","value":"Interchangeability of relevant cycles in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1431767"}},"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":"Q1972676$D55206C2-C85C-4E58-A97C-AEE004878CC6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ab183b86139033d262fef23793e0a02b95576b6a","datavalue":{"value":{"text":"Interchangeability of relevant cycles in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1972676$D59AD44C-3954-42AC-B953-CED01318DC49","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b28785d2262405dfd5654319d7dc26c1214c219d","datavalue":{"value":"0939.05048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972676$6273BED6-F001-47C4-B126-4D2972357922","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3005f75a484578aad126c92d543c5643a7f1885a","datavalue":{"value":{"entity-type":"item","numeric-id":1972675,"id":"Q1972675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972676$836735A4-565B-45D3-B42C-4E63671EB451","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"790cada3abb7a0b29a8651854d04418b74527b24","datavalue":{"value":{"entity-type":"item","numeric-id":228049,"id":"Q228049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972676$258C1AD1-1A19-47B3-A7F9-62A63B802371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a93e0417a54db04a001534bc4b28927ef06fcb34","datavalue":{"value":{"entity-type":"item","numeric-id":176199,"id":"Q176199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972676$22920C87-8903-47D0-B3E5-959D99AF4EE0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972676$D07C7408-0EEB-49DD-85BC-B58B3FFC3602","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fd2d1fe82fa6e2c6e97c965e0ca8e16ed58495a5","datavalue":{"value":{"time":"+2000-04-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1972676$618CE03B-3AB5-4E17-95BA-187E64A57E20","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9ba897d526c10359930f8283e2a3f0596a8c1973","datavalue":{"value":"https://eudml.org/doc/120353","type":"string"},"datatype":"url"},"type":"statement","id":"Q1972676$DF18C6C0-F7FE-47A2-9616-98E09AA16312","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"1d82714198c7d719c13019273051a832ca4bd10c","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_7/Abstracts/v7i1r16.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1972676$4A4DDDA7-6C09-49B4-ADFB-A8C38C17479A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c6a916795dd3f6602c7517a7a7e20c39762caadd","datavalue":{"value":"Summary: The set \\(\\mathcal{R}\\) of relevant cycles of a graph \\(G\\) is the union of its minimum cycle bases. We introduce a partition of \\(\\mathcal{R}\\) such that each cycle in a class \\(\\mathcal{W}\\) can be expressed as a sum of other cycles in \\(\\mathcal{W}\\) and shorter cycles. It is shown that each minimum cycle basis contains the same number of representatives of a given class \\(\\mathcal{W}\\). This result is used to derive upper and lower bounds on the number of distinct minimum cycle bases. Finally, we give a polynomial-time algorithm to compute this partition.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972676$9E212BB0-3A43-4D11-989E-E51F7FDA609D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972676$4AAB3B09-E020-4C39-BDB8-880165FF9426","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f2e81f5d3d80da0ada665d1153c185f52e4b779e","datavalue":{"value":"92E10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972676$FC6B783E-FD8D-4D74-AB16-41D0471F0214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972676$69D23532-7DF5-41A3-87D4-D1DA13C72A73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505a49771a29a1df80db47f27f0ca3c9ddd29e48","datavalue":{"value":"92D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972676$F8211B05-CF07-481F-8382-DEF68D301411","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d08a238ef3c6452b81d82106d6ca23610ebf0bc2","datavalue":{"value":"1431767","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972676$5C71EE40-8241-4AF8-B2D2-6F0A1547A73B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef8fd65f14aef92513ba4eeff30598665772c241","datavalue":{"value":"minimum cycle basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972676$A940B133-48D7-42AD-B201-4CE40FA6F39C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3332b4c3ef8914f29a4871d136367e853094bde1","datavalue":{"value":"relevant cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972676$159C747F-10B0-4DE1-82B5-1233BDE6E302","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":"Q1972676$07E1A481-D971-43EE-924F-28817C5E46B5","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"153a003fc6535fc33db04d1cd8b980408dd51de9","datavalue":{"value":"bafkreiesycv6rkw2zhe3axeemfwkkodgueqz3p2byfhbdeyiwlutdoynfq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972676$0ACDFF65-25D2-4A9F-A24A-36E443108089","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23d5a2d919c972650151e029ae949ee30a1a0045","datavalue":{"value":{"entity-type":"item","numeric-id":1378498,"id":"Q1378498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3f8af0d8076c5022689977a5c0d2dfe0d25703c","datavalue":{"value":{"amount":"+0.8445443511009216","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":"Q1972676$22942768-F408-4190-80F2-9CB5C690C7D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b3c93802a9428d84aad49a9389990146a05fbfe","datavalue":{"value":{"entity-type":"item","numeric-id":3525552,"id":"Q3525552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d30f43fb3596ea56d92abf09fa27cef105118d93","datavalue":{"value":{"amount":"+0.792879581451416","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":"Q1972676$67E7D85E-693D-46C3-8E4D-F9CC63CCA636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a97438fb81863a6d2ddf0f503f21bc104d7f849","datavalue":{"value":{"entity-type":"item","numeric-id":458496,"id":"Q458496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f633c4e618dcf520d98c917ded66369734281272","datavalue":{"value":{"amount":"+0.7772687673568726","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":"Q1972676$48FA1150-643A-445E-90B7-3CD62386B5CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0c9fb1485236e7335a6d836a91d81a488a25222","datavalue":{"value":{"entity-type":"item","numeric-id":3637310,"id":"Q3637310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e25a644aae8b3a84f49a58f121558e53c0dfff9","datavalue":{"value":{"amount":"+0.7649264931678772","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":"Q1972676$6A268308-1866-428C-BEE5-1F19AC799737","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1972676","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1972676"}}}}}