{"entities":{"Q1118604":{"pageid":1129353,"ns":120,"title":"Item:Q1118604","lastrevid":69684891,"modified":"2026-04-13T08:41:49Z","type":"item","id":"Q1118604","labels":{"en":{"language":"en","value":"Branchings in rooted graphs and the diameter of greedoids"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4095484"}},"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":"Q1118604$140B79B7-8381-4D16-9435-47096FC2334A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d1ac68828c34f918d98714e1a172bc606be98986","datavalue":{"value":{"text":"Branchings in rooted graphs and the diameter of greedoids","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1118604$A589ACF6-87D5-4DA6-A82D-A5D292A2D18B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"606ebb59a2459c8905310dbc38589c86a4241ba0","datavalue":{"value":"0669.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118604$04E286B5-2ECF-41E7-8C1D-E3740EEBDFD5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"131f843c24977f5b39e8f9a1c7e292e2365fbf45","datavalue":{"value":"10.1007/BF02122803","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118604$960443F0-5F57-4DA9-BA2F-24EC6EB601BF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cfe0a5f87b19df88cac5722a0ca652a24041a387","datavalue":{"value":{"entity-type":"item","numeric-id":189313,"id":"Q189313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118604$50E4B8AC-7631-43E5-B423-21D3E67ABF8D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118604$FC84B401-255D-47AA-B0B9-EA188A837F5F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1118604$A121EAB6-252F-4929-9F3C-31B7D2418EDD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"11312cd7f01e56c73e59e7397c95b5a31c417cc1","datavalue":{"value":"Let G be a 2-connected rooted graph of rank r and A,B two (rooted) spanning trees of G. We show that the maximum number of exchanges of leaves that can be required to transform A into B is \\(r^ 2-r+1(r>0)\\). This answers a question by L. Lov\u00e1sz.    There is a natural reformulation of this problem in the theory of greeoids, which asks for the maximum diameter of the basis graph of a 2- connected branching greedoid of rank r. Greedoids are finite accessible set systems satisfying the matroid exchange axiom. Their theory provides both language and conceptual framework for the proof. However, it is shown that for general 2-connected greedoids (not necessarily constructed from branchings in rooted graphs) the maximum diameter is \\(2^ r-1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118604$4E16AA2D-8A57-4B82-BFAA-8B6AB5622BED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118604$49B09DF8-4181-4FFC-955C-DDEC0A382CE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118604$E3A96800-733E-4C00-8048-C70E8C92F557","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118604$64B2471B-1A7F-4FD1-BF45-0852EA75A2D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118604$F9CFAA66-50F9-4B41-89AB-A48A112303CD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9c8f11c0be7072e63d9b713bd63c845cc6ae2bc6","datavalue":{"value":"4095484","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118604$2556D764-C3E7-428E-85C7-34B9F0539F3B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a24dc34fb67873a8c9a408b77d86ca4ed97e73be","datavalue":{"value":"2-connected rooted graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118604$D9FE6E9C-0127-4DC8-9063-4D7436C2A686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1fd374a0049b4a729d8b7a818f6d7dfa7547e432","datavalue":{"value":"greeoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118604$ADEA3065-920D-4B4A-9FD3-77DB145CE5B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34db4a88ede3b56fade0a465850feea92cc8538c","datavalue":{"value":"maximum diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118604$444C3587-BC16-4596-BB75-8521B5D5C78C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f9dda206f47fbc717ebe09efed1bb13a021d432","datavalue":{"value":"basis graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118604$54A0A490-610A-4EFB-AA4E-7D307C5F9E67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b6ff972d0d81d57033c8f0ffdb26bb12e00b92e","datavalue":{"value":"2- connected branching greedoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118604$80D80DD4-3230-41EC-9154-4F299414B418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93d95d8b6700b5b27553268033791439b77fc3eb","datavalue":{"value":"matroid exchange axiom","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118604$E9507732-634D-4CF7-8673-7CFB8AFD3027","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":"Q1118604$FD45CF00-8EB3-4262-9463-BFED6B40ED39","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7672f1c23668da17ca11563637b351579e9a6eb1","datavalue":{"value":{"entity-type":"item","numeric-id":3882496,"id":"Q3882496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118604$1854449D-466E-4198-A9BA-CB4E435F52CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e6eed23148f50e2dc5f877a0f3ad486a9c65d6b","datavalue":{"value":{"entity-type":"item","numeric-id":1156160,"id":"Q1156160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118604$B953D470-FC67-404E-BB14-5E4B8B5F0526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07b5b091c2202899878af2def6b6dc44beb0fe39","datavalue":{"value":{"entity-type":"item","numeric-id":1101115,"id":"Q1101115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118604$1D3E56D2-E545-4D8E-980C-B889361BA07D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e60978c83a38579e60efd74251166e0089699f1","datavalue":{"value":{"entity-type":"item","numeric-id":1069309,"id":"Q1069309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118604$3FFF2D01-52AD-42DB-AB5B-B1388EEC7D8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d95934222a6de7a586d201fcbdb4e17ec0b5dbc8","datavalue":{"value":{"entity-type":"item","numeric-id":1065391,"id":"Q1065391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118604$55E58120-240B-40C2-8293-2A22751BAD16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29aacb4676721e7bd3d76c498d8442c90d28e937","datavalue":{"value":{"entity-type":"item","numeric-id":594882,"id":"Q594882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118604$E4321EF1-2221-40FC-BAD7-E400ECAF618B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9321fa0d3d838ff71f827d3db6dc7538a7f5e718","datavalue":{"value":{"entity-type":"item","numeric-id":3323971,"id":"Q3323971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118604$F31858E3-E2F8-4EFF-B06D-76615BB0B615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86ca986d3627a6f1c352919dc288ddf1185152ee","datavalue":{"value":{"entity-type":"item","numeric-id":3716815,"id":"Q3716815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118604$B0CCA02E-63E3-4844-A42E-685A019616C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a406a6b5ed6c9309b8ad55d05548d72147f7813","datavalue":{"value":{"entity-type":"item","numeric-id":2266020,"id":"Q2266020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118604$2D90A8D3-5B95-4B14-A8F8-4B8734853368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7dc1c57e156386d898b655976f55f37addc49837","datavalue":{"value":{"entity-type":"item","numeric-id":4012035,"id":"Q4012035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118604$C52396D0-F664-4D78-8AB5-B0D5C2E48AE6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76d7eea4fb0e614eb3523b1f266d84b71d5bccfd","datavalue":{"value":{"entity-type":"item","numeric-id":708389,"id":"Q708389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8671c4ef0d9c69c916ad2b65b2cddb73ed98a771","datavalue":{"value":{"amount":"+0.9294233","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118604$2414E32B-2D69-43F3-A7F4-1D33A25475E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5c0777cd80542786f24b254511898f355bafe06","datavalue":{"value":{"entity-type":"item","numeric-id":4013425,"id":"Q4013425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21e125039e5ba9c27bf605fc0d25809807737ac5","datavalue":{"value":{"amount":"+0.8971591","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118604$3144223C-D91C-44B8-8DB2-05239996220D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e21c761440b50786fc44d4dfbeabfd21f8a1ec3","datavalue":{"value":{"entity-type":"item","numeric-id":4201398,"id":"Q4201398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9107d73cb1ce194dd334112d380e213a758af32","datavalue":{"value":{"amount":"+0.8868143","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118604$F2E8266A-8CC3-4D1F-848D-1564077860F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e59c20ebf4aa3946ea84f158c2d552ee40b2d39","datavalue":{"value":{"entity-type":"item","numeric-id":967314,"id":"Q967314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c96867ecfe5f710de321aba905ea063a258d91c","datavalue":{"value":{"amount":"+0.886691","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118604$EFC168E9-72F7-425C-8803-8003A99D9C13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b256e20e82b1ccad6ff2474a4d0e01f2f6cead8a","datavalue":{"value":{"entity-type":"item","numeric-id":4944671,"id":"Q4944671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b717907baa4a754c60c0618327696c0e59efcbbf","datavalue":{"value":{"amount":"+0.8864838","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118604$62F9EB0C-DE06-47F4-9771-7B9FFC55906B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7e4a6f0be1094a20971b0e6182a5c5e81c4c473","datavalue":{"value":{"entity-type":"item","numeric-id":2642007,"id":"Q2642007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"285baeac482248783a5bd2d3487cb9ea7589999f","datavalue":{"value":{"amount":"+0.88560766","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118604$AFD520AE-E9A5-4F9B-B83C-1016C53A68CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc19b71c1035d12b81a826661256987289f1704e","datavalue":{"value":{"entity-type":"item","numeric-id":5421816,"id":"Q5421816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27516c2a173426e78158027a3b738bca8f6febb2","datavalue":{"value":{"amount":"+0.8839867","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118604$C5FBF85A-E3D4-463C-9AFA-0E962BE3864D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03fe97747cad7cdf802b7d2e850531a0351459b2","datavalue":{"value":{"entity-type":"item","numeric-id":5005108,"id":"Q5005108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a06b929c9b74bc13f6bb0a5ff64f08148581601","datavalue":{"value":{"amount":"+0.8835168","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118604$16327F7A-1422-4995-9B51-D3D925F19C97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"838eac088536122c6fb60a67142be08a60d1ec8c","datavalue":{"value":{"entity-type":"item","numeric-id":2192110,"id":"Q2192110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"760c0b043eced4a8d1a6278efaec7b24ee250254","datavalue":{"value":{"amount":"+0.88351667","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118604$74E018A8-4354-4707-A2B4-0E3C666C735E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"639faca758c7c7449ab765af9cf254cc26893a28","datavalue":{"value":{"entity-type":"item","numeric-id":5012367,"id":"Q5012367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"000fa2e113e1100e7cf785c641ef3a877eee0971","datavalue":{"value":{"amount":"+0.8818487","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118604$281EC2E2-77C2-4DF2-A740-C2F8B0E4B864","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Branchings in rooted graphs and the diameter of greedoids","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Branchings_in_rooted_graphs_and_the_diameter_of_greedoids"}}}}}