{"entities":{"Q1378498":{"pageid":1389238,"ns":120,"title":"Item:Q1378498","lastrevid":67507143,"modified":"2026-04-12T18:28:30Z","type":"item","id":"Q1378498","labels":{"en":{"language":"en","value":"Union of all the minimum cycle bases of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1117994"}},"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":"Q1378498$E8288420-1251-42ED-9594-8DC8B7620B69","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cc639ff34d3b66fababf8536841b3ee3bae88d3d","datavalue":{"value":{"text":"Union of all the minimum cycle bases of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1378498$AAB89C2F-F35C-4581-A251-8CDCC5836AE8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0d433ce2e3bb347666d856af293be899bf73e1a2","datavalue":{"value":"0885.05101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1378498$BA63FA8D-8CCB-4418-A1C1-20A3F26CC3CC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"49acafa58ce2e3c6dc70c0af6cfc0c5e84c46bdd","datavalue":{"value":{"entity-type":"item","numeric-id":1378497,"id":"Q1378497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378498$DF80AB20-24BA-4BDE-875A-7B9E99B26346","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":"Q1378498$933AD032-4E2E-4CB2-9CD0-7DD7620ADAF2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8056832bb4b81d87f3d05c5145b710c71de827c5","datavalue":{"value":{"time":"+1998-02-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1378498$CC3F10F5-72FC-4FCE-8457-EA06B8468450","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3d43331dc61b18a6ca2b41c1eea5a487dc593294","datavalue":{"value":"https://eudml.org/doc/227545","type":"string"},"datatype":"url"},"type":"statement","id":"Q1378498$4F88FF1D-DFA2-48D0-8CB3-20C61FA73A8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"a8ee9b0e26b209e3ea1902e4f9369b426093275b","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_4/Abstracts/v4i1r9.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1378498$AA7D3157-D746-4378-A3F6-4D8C3645260D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fc7cfeaa924b792b65262db0f7385e89b80f7c9c","datavalue":{"value":"Summary: The perception of cyclic structures is a crucial step in the analysis of graphs. To describe the cycle vector space of a graph, a minimum cycle basis can be computed in polynomial time using an algorithm of \\textit{J. D. Horton} [SIAM J. Comput. 16, No. 2, 358-366 (1987; Zbl 0632.68064)]. But the set of cycles corresponding to a minimum basis is not always relevant for analyzing the cyclic structure of a graph. This restriction is due to the fact that a minimum cycle basis is generally not unique for a given graph. Therefore, the smallest canonical set of cycles which describes the cyclic structure of a graph is the union of all the minimum cycle bases. This set of cycles is called the set of relevant cycles and denoted by \\({\\mathcal C}_R\\). A relevant cycle can also be defined as a cycle which is not the sum of shorter cycles. A polynomial algorithm is presented that computes a compact representation of the potentially exponential-sized set \\({\\mathcal C}_R\\) in \\(O(\\nu m^3)\\) (where \\(\\nu\\) denotes the cyclomatic number). This compact representation consists of a polynomial number of relevant cycle prototypes from which all the relevant cycles can be listed in \\(O(n |{\\mathcal C}_R|)\\). A polynomial method is also given that computes the number of relevant cycles without listing all of them.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1378498$30BD7A65-46A5-4478-B52A-7EBAFD97A396","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1378498$EFFBEC12-F1D0-4118-A0B1-1E855DE98224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1378498$9D1A8D0B-84AE-4319-9F54-50CA5CFBED30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1378498$A520C49A-B621-471C-8484-255DEB82FBF3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b8c228fe0d902c6c1e8739c7d51ad1d8d770e4c","datavalue":{"value":"1117994","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1378498$A03669B2-34E4-4677-97A4-A467FA24D25A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a8022e6be650e4a6ee19e7e291c2b92f8057967","datavalue":{"value":"cyclic structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1378498$7BE93A80-CD69-4FD8-B7E2-8BE64F7F745F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3ed37ab948922cded531367088d8dfc3aca1119","datavalue":{"value":"cycle bases","type":"string"},"datatype":"string"},"type":"statement","id":"Q1378498$C3643FC7-378B-412E-8289-8AA8966CA761","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"144c9ac57d6b4c1d96e5ca1ecf5533efd0b17d82","datavalue":{"value":"relevant cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1378498$36B080FA-FA0F-4E97-A8CD-2821A7BFF219","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1378498$CA0E3BD0-95B6-4476-847C-3DC5172301DC","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":"Q1378498$543A407B-FE13-4705-ADDA-D6CEDE6223CA","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"5ce37771b3e4df2df17dee9e9d6f7b018e34bc0b","datavalue":{"value":"bafkreib7vrmeqxc3pjuy33waauh542mvei4wbsf42wknhjwbuse4a32ska","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1378498$CE1CCC47-A798-4E91-92B8-F9EE59998B2E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e6cd4a82375c6fe783f190aa972c6cd2681e107","datavalue":{"value":{"entity-type":"item","numeric-id":1972676,"id":"Q1972676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b950a4b2e0a3e2cf58574b67963cad6eb04a6d4","datavalue":{"value":{"amount":"+0.8442507386207581","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":"Q1378498$17E563F6-4F9D-466C-A779-73C94BF6F7AA","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":"d47cf19482f1d5b12b174d9c126a4a9556178e02","datavalue":{"value":{"amount":"+0.84157395362854","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":"Q1378498$012DB7AB-AEF8-4719-838E-C7C4B14BA435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6e1d9bc0e4380ff89b31efd285c7d3c8ebef5a6","datavalue":{"value":{"entity-type":"item","numeric-id":2930281,"id":"Q2930281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9002f24737ad9d5582bc0c2ea56822b5fe2f1b91","datavalue":{"value":{"amount":"+0.8261758089065552","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":"Q1378498$71FF6734-24EF-4462-A599-A6FD01F540B4","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":"999d41ae1e9f890fc9c94ee58f0bc75dfc0a8eb9","datavalue":{"value":{"amount":"+0.8184912204742432","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":"Q1378498$E18BD131-3A9E-4EEA-A146-BA5AE3EF2368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4611482942948061e55148da343d808edb9309a3","datavalue":{"value":{"entity-type":"item","numeric-id":1882477,"id":"Q1882477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11445e5643128ed0dce877a36b16b5a5e170a00a","datavalue":{"value":{"amount":"+0.8172364234924316","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":"Q1378498$EA28887C-471A-41D9-848C-6BF290778525","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Union of all the minimum cycle bases of a graph","badges":[]}}}}}