{"entities":{"Q1105381":{"pageid":1116130,"ns":120,"title":"Item:Q1105381","lastrevid":69653616,"modified":"2026-04-13T08:28:37Z","type":"item","id":"Q1105381","labels":{"en":{"language":"en","value":"On finding optimal and near-optimal lineal spanning trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4058882"}},"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":"Q1105381$54EBFFBE-6457-40B0-9276-A30E5C819C94","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b23ca3b755a3610f286a47f91145cd12355083aa","datavalue":{"value":{"text":"On finding optimal and near-optimal lineal spanning trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1105381$DE283FC3-0C21-4509-8DA7-F92A62EE92B8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7c73ef43d68104e90ecaa67ff92880097e200cbe","datavalue":{"value":"0648.68074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105381$96DC2D46-140F-4B7D-B416-3F014A2A1EBD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"564863a7efbc7b9ed21242f78eb960e537d33551","datavalue":{"value":"10.1007/BF01762131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105381$547A22D7-4799-4E03-8E65-C523A7EAF673","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"057c48278a1d014d58f7703e66b1dc164eccfbc4","datavalue":{"value":{"entity-type":"item","numeric-id":175527,"id":"Q175527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$71064C19-E4B2-496B-A64B-87EDD1BCD184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"912a686097f499caded7625c01b65e652133bde6","datavalue":{"value":{"entity-type":"item","numeric-id":429661,"id":"Q429661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$43E17357-E803-4178-B5D9-BB1D7E0EF19C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d288423df0deba1f237a49670693efc500bb8d57","datavalue":{"value":{"entity-type":"item","numeric-id":293396,"id":"Q293396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$0997BEAC-FC36-4F34-822A-A4C71F65CAD4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$7E9F2AF3-559B-46FC-B1C4-19A14C80EB05","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":"Q1105381$C623C904-AE8F-4F9E-B78E-498B38D6843B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105381$3ED4CCB3-6773-48E4-AD70-EF28058E058B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105381$CE604DD9-BE3C-4EE6-A1C5-99E8F7214D06","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cfcd71c698bf7790076c5ed1dcca5b8c32f1b616","datavalue":{"value":"4058882","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105381$1F82FDF4-6262-435C-8ABB-EACE665A0F35","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00fab533cd38d922e3a2c54a153ccdfb1b56ca89","datavalue":{"value":"constraint satisfaction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105381$8076BFE4-03A9-4DF0-9D55-0703B15A8D86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff7bf11626141f10491819543bc6e69eb57efdf3","datavalue":{"value":"depth-first search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105381$05CC6108-A085-4938-ABE1-0BDFC5C5871B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105381$E0E167AE-1134-471F-9F91-275380D23B14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac14383556dcaa2e1467a20bdb2e0a630f9d1c34","datavalue":{"value":"lineal spanning trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105381$BDA227AF-0AF7-494C-AE9E-0EFF69A99D63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1105381$F1F93D4B-43A7-4898-B59F-0D25C5148BE5","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b6900878437b36a413c55274a85657f8de9aa484","datavalue":{"value":"Q57360176","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1105381$16648C65-B695-40BD-B3A8-0ADF45DA2A8A","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":"Q1105381$5DE555B2-02E6-4BF9-AEA5-8568DC13F1DC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$497C25A9-381C-4C6B-8EED-5853B8271C35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$58897C2F-D5A0-4BC3-9EE6-0FEF1FCCCA59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9a872690aae65aa8cbfced9522c07629e0a8e21","datavalue":{"value":{"entity-type":"item","numeric-id":3862380,"id":"Q3862380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$69D55DFB-FF48-4C8B-8436-828A01A32916","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":"Q1105381$F63A39BE-D6E6-4ADD-B14C-5B5A024FB1D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb90704920f5f134b6d172f818d255b32ae4d678","datavalue":{"value":{"entity-type":"item","numeric-id":1204865,"id":"Q1204865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$43A1E7EC-2CD7-4599-984D-D3D1E5C39208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$395EBDEA-B6D8-4D7E-825E-DA91F799822E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3b7f421571a2d71ea5ce0028ff1487f50f83aed","datavalue":{"value":{"entity-type":"item","numeric-id":3753502,"id":"Q3753502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$EDA30F10-732D-4606-90D3-977D232E7F86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"929774d1e3f2e6ce75397119ad275b9992d726fd","datavalue":{"value":{"entity-type":"item","numeric-id":3309631,"id":"Q3309631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$B5CC32C7-FC63-4AAF-9094-BE6684E4A251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57ef3857062b7526f0053324aedc3e9d5ac4de1b","datavalue":{"value":{"entity-type":"item","numeric-id":3725546,"id":"Q3725546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$A2B9C0F8-8926-4CAE-B897-5F3F4C515835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c40ee71aca2effb6407678cebd17a104b4af33e","datavalue":{"value":{"entity-type":"item","numeric-id":3659812,"id":"Q3659812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$7447D898-9E5C-4169-AB1D-C713A19EB31F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c53238d3d5db8f813b51207e063ca7a3d3466d9","datavalue":{"value":{"entity-type":"item","numeric-id":4552272,"id":"Q4552272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1105381$5CA687ED-5C77-400A-A5D0-E7F4A6CCD9EA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2419ffaf7fa371568ec6df12b1febeb7e1eacc3a","datavalue":{"value":{"entity-type":"item","numeric-id":1840509,"id":"Q1840509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f33bcadebc9b87620d47fda5c125b72b57cddca","datavalue":{"value":{"amount":"+0.91918933","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":"Q1105381$3D99C2C9-669B-445C-AB8F-DD1DAC40B0AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35120798f1f0111bf4b37964fcc032c57c89cbb2","datavalue":{"value":{"entity-type":"item","numeric-id":4217304,"id":"Q4217304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c0e05dee67113e875a7445da466aff7f7e5a133","datavalue":{"value":{"amount":"+0.91509825","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":"Q1105381$B44A65B1-3333-44B2-AD6B-53BB314E632F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"832f39ccd4e73afc33d427ac9d7ac5e2903a4612","datavalue":{"value":{"entity-type":"item","numeric-id":5096340,"id":"Q5096340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5319f4ae47cb24f72f867b00413d0722f484caf","datavalue":{"value":{"amount":"+0.910385","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":"Q1105381$1BFE7C78-15C8-461A-8729-7149BCA8F99A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7973478c88500e62f0fc24ff6fcc8f9e5d622a19","datavalue":{"value":{"entity-type":"item","numeric-id":1391300,"id":"Q1391300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5319f4ae47cb24f72f867b00413d0722f484caf","datavalue":{"value":{"amount":"+0.910385","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":"Q1105381$C14D6753-C97D-4BE7-A641-BA7C87427DDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da84593a6c41a4d9b01ea3986048eee8f5ad0477","datavalue":{"value":{"entity-type":"item","numeric-id":2817593,"id":"Q2817593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b63a5f6b9c417f64dc5f89ed5d6ef043d7cac80","datavalue":{"value":{"amount":"+0.9088417","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":"Q1105381$3F4A30A7-8B0B-42AE-AC56-B125505E4161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39cd577c09d0992ef9bda920a739b699adfad57f","datavalue":{"value":{"entity-type":"item","numeric-id":2081596,"id":"Q2081596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb11b19345544830024c67e138c724e2936dd2a2","datavalue":{"value":{"amount":"+0.907975","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":"Q1105381$40D61650-C49E-43B0-808D-89FEDD634A85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35bc56fb939e0452ee4f477500b796cc6533f9c3","datavalue":{"value":{"entity-type":"item","numeric-id":5096337,"id":"Q5096337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c8c53e5ba06d60d565c7e1c502ce0906b74e6cf","datavalue":{"value":{"amount":"+0.9041513","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":"Q1105381$E2944CA7-30BE-48DF-97FC-3CAD602EF103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f39a99ebcba50ff6da74c6ac578e75368e704ea0","datavalue":{"value":{"entity-type":"item","numeric-id":1391297,"id":"Q1391297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c8c53e5ba06d60d565c7e1c502ce0906b74e6cf","datavalue":{"value":{"amount":"+0.9041513","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":"Q1105381$C5F94134-277F-49CF-BF42-15161303467D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66d67324835f77f5d2b4751e7de32d2c2e90908e","datavalue":{"value":{"entity-type":"item","numeric-id":4369866,"id":"Q4369866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f97e4a8b028ecf983ff56fa8d7c4113f0b64c244","datavalue":{"value":{"amount":"+0.903989","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":"Q1105381$08E1686B-1CDB-4022-9790-035E6C59ED0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"131d36bfc52cd4928393a6b652d9d6b2cef4ccb4","datavalue":{"value":{"entity-type":"item","numeric-id":2753956,"id":"Q2753956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27a8869fe3a175c9670c979a57a207a13682ee2e","datavalue":{"value":{"amount":"+0.9039254","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":"Q1105381$A35F2D63-6392-47A3-9452-78E128EAE58E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On finding optimal and near-optimal lineal spanning trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_finding_optimal_and_near-optimal_lineal_spanning_trees"}}}}}