{"entities":{"Q4632175":{"pageid":6661756,"ns":120,"title":"Item:Q4632175","lastrevid":82292702,"modified":"2026-05-06T20:33:25Z","type":"item","id":"Q4632175","labels":{"en":{"language":"en","value":"A polynomial time algorithm for finding a spanning tree with maximum number of internal vertices on interval graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7048077"}},"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":"Q4632175$AB11C8AA-2BBC-4248-B51F-19C24AAE4DA2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7583d2112bb1674d3a05e594181f1e9a539a3437","datavalue":{"value":{"text":"A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4632175$2CB62FFE-DE5B-4EE3-BF68-1CEF1F24E2ED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9587a24308651bd1b08514ac20518294e361969c","datavalue":{"value":"1475.68249","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4632175$D9EAD6B8-F616-49EB-AAC6-A106FADF3078","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"648b5085e84cdae89fae539ee34d755227b7c3f0","datavalue":{"value":"10.1007/978-3-319-39817-4_10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4632175$2AA28074-CFEC-44B7-A96F-B45F4D88232F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d43525fabb6a8a41eb20979349ebae83da1c4ea4","datavalue":{"value":{"entity-type":"item","numeric-id":1794285,"id":"Q1794285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$E0D0EEC9-4BBF-4964-ACFA-3E58000CE477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"81e6e2da60720a54976c79e6881baaaf0cafc813","datavalue":{"value":{"entity-type":"item","numeric-id":1029346,"id":"Q1029346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$0026BA59-30AB-41C9-AEBF-0E2E1419A954","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0dc15826b00ed1659340bf5ef9eb4e0c8cbd4303","datavalue":{"value":{"entity-type":"item","numeric-id":261347,"id":"Q261347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$4B741BCC-6544-401D-84B6-63C4DFED58E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ec8fbe8d522bffba86db602aec04dca122f250a","datavalue":{"value":{"entity-type":"item","numeric-id":243606,"id":"Q243606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$55A121B5-F815-426D-BBA0-C3569540E9EC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"039449918372fd36372960c159b1f017e2991028","datavalue":{"value":{"entity-type":"item","numeric-id":3188827,"id":"Q3188827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$63DE0F65-00DC-4434-8632-EBE7D0290295","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0368fcac4180a6b094041fe719d3c9855e55cde6","datavalue":{"value":{"time":"+2019-04-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4632175$E001032C-1D29-4066-A645-2E0C534763C5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4632175$841C0C35-A310-41A5-96A0-6C44293A2B50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4632175$81BA6412-0DEE-4E88-88E6-AFDBC1D7522F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4632175$6C062EF1-7F5A-4466-9504-19DCD1808FF1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"147c657910d02a714041c78f23d123f8b7564222","datavalue":{"value":"7048077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4632175$DBE780A2-C792-4D7C-8D3B-32F49DB879A6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b5d2fa24c579b2baeef4d0446de7aa9ba4289043","datavalue":{"value":"polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q4632175$D04AAAAD-2547-4ACF-BA03-D823DEFB3FD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q4632175$3620A026-A454-43DF-954D-7D46DF658FD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"065eb39987c501f25196207042caaa443bd0ec8c","datavalue":{"value":"maximum internal spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q4632175$542F20FE-CEC9-4EAB-8A1B-27CB41EEE9C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a949c568749d2f4337e1772be827516d5211abc","datavalue":{"value":"interval graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4632175$0C5EF906-848E-4C59-B7C9-6AA17212B3E1","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":"Q4632175$E342EC9B-4E80-45E5-BD1A-FA42742ED585","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7f6663157c8045e3ef3c8f07baaedbdd4ee1898c","datavalue":{"value":"https://doi.org/10.1007/978-3-319-39817-4_10","type":"string"},"datatype":"url"},"type":"statement","id":"Q4632175$E35A0A8C-C023-4C16-9CC1-FA1C9A55E874","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"af46c75744919bd93690d639b76c5a4380bc677a","datavalue":{"value":"W2497553818","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4632175$EA60E37E-AA3B-47AF-AA17-C1F0EF94796E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"db695381606ba322df78c7a9c05e7660a22ed7b4","datavalue":{"value":{"entity-type":"item","numeric-id":3888545,"id":"Q3888545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$3B2D7082-5F70-4FA1-8B4D-DF2102CFE06E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db4ad447365e96853230d4e27c13c56f7b046fd9","datavalue":{"value":{"entity-type":"item","numeric-id":1939668,"id":"Q1939668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$5F430D49-BDDE-47F0-B223-ED032D8FDFCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ee8423ce1c7baba5939a214a6601ab4ed11f4fe","datavalue":{"value":{"entity-type":"item","numeric-id":988577,"id":"Q988577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$A8107A98-D8D6-43D2-8CEB-ADD6BA309EA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26a018ea6151f4aff1056d77373c1793090005c6","datavalue":{"value":{"entity-type":"item","numeric-id":2427493,"id":"Q2427493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$51FB1C4B-9EDE-44A6-A860-029AF2044CD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5a7a39aa199002e2691f4bb58990ae8ff192167","datavalue":{"value":{"entity-type":"item","numeric-id":2429363,"id":"Q2429363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$A30DEA6F-3B17-4230-821A-F3AC54E97438","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bd5c9c393ea8f8f8133790fc4e28bcfdea8f7de","datavalue":{"value":{"entity-type":"item","numeric-id":1936242,"id":"Q1936242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$D7E7AC79-6F28-4268-A9E9-3959EE8933DD","rank":"normal"},{"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":"Q4632175$55B8FBD7-551B-4273-A9C6-E3DFF07D6655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7025670da98639c741b2f1992cb7ce4bc66c023","datavalue":{"value":{"entity-type":"item","numeric-id":3183476,"id":"Q3183476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$C6A8CBC9-1785-4901-8E09-39246558CFCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34a0e09f3f008879e80cbe6c72172293bd53f825","datavalue":{"value":{"entity-type":"item","numeric-id":1045112,"id":"Q1045112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$CDFA9EF7-AD3A-44C1-8EEE-0C7C91AEE2BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69686f257911af47e82468265d7acc6a22c920f3","datavalue":{"value":{"entity-type":"item","numeric-id":5900777,"id":"Q5900777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$BD649683-A343-45D4-926E-3C487F0DAB31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e51e2102c385737775fe0be2e00ca1f5673996b","datavalue":{"value":{"entity-type":"item","numeric-id":3369936,"id":"Q3369936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$E0A2B24D-36BC-4E8B-99CF-22F245D5C8D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b8fd6c4a4937aa29062014bbedbf8a512869de2","datavalue":{"value":{"entity-type":"item","numeric-id":2380066,"id":"Q2380066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$E8EAB1F5-91E5-4CCB-9933-32B1DA2E451B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fac5b2aed6bba5920102f6439b988da0d6ce1b54","datavalue":{"value":{"entity-type":"item","numeric-id":1034535,"id":"Q1034535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$2C551117-BDF9-4226-843F-B05ECDFF501D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99339c25b72ec5e48b857d76d56224728b606f96","datavalue":{"value":{"entity-type":"item","numeric-id":1167739,"id":"Q1167739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$30C476B6-92F3-4BFC-B574-FE5A2A44CCF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce9f0586723a058ecad8482b4ebcd3a505b45626","datavalue":{"value":{"entity-type":"item","numeric-id":2867096,"id":"Q2867096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$E7B00454-CE5A-4FD9-8BD3-1365092EA93B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b66d43343b5e258838f8347f60921b66aa51177c","datavalue":{"value":{"entity-type":"item","numeric-id":911770,"id":"Q911770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$32D2BD76-E447-466A-8FC8-23DB52C19AA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f219e7fd5b0d461aa31ad2849ba73aba72b7e6e","datavalue":{"value":{"entity-type":"item","numeric-id":1111566,"id":"Q1111566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$49EAC5E2-7024-47A3-9DFC-813FEC719A5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81506a39c3044bf3e3244a24ab679e68cca8f790","datavalue":{"value":{"entity-type":"item","numeric-id":2921450,"id":"Q2921450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$D157F413-64E1-4B64-915E-FC8A247B5BF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2adc10b543d5855e45e855ee2d068f9b4c04628c","datavalue":{"value":{"entity-type":"item","numeric-id":2942652,"id":"Q2942652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$C7867714-ABB0-4AA3-A155-B0D83B178F14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b07b5dcf0b43c9f49e2d29db88bee73b1cb11be","datavalue":{"value":{"entity-type":"item","numeric-id":1886097,"id":"Q1886097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4632175$DC8D3E55-23B8-4F8E-99DA-EB87F57CD701","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ef1db25d15eb9252220442ffae679a212f77589","datavalue":{"value":{"entity-type":"item","numeric-id":2636496,"id":"Q2636496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9d304c1a2b05e8f2dddfcc9c93026efe8642d61","datavalue":{"value":{"amount":"+0.977992832660675","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":"Q4632175$130BA541-DBEC-4427-AEFC-9D7BC1E501C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebc5cd88bf8962b617fd59adf3723350a3bc432d","datavalue":{"value":{"entity-type":"item","numeric-id":2656175,"id":"Q2656175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91ab922082387530794bd47579895aa6051b4780","datavalue":{"value":{"amount":"+0.8684581518173218","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":"Q4632175$DB72C255-A262-42FF-9DED-8FF05938B31F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29be19d5178a8133ca3519d5af875d9c90717229","datavalue":{"value":{"entity-type":"item","numeric-id":2091107,"id":"Q2091107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3acf7f2fd17a1aaa9cb790591775732545e73550","datavalue":{"value":{"amount":"+0.8490694761276245","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":"Q4632175$431DABE1-5814-4313-966F-07E118A708DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f494ff6b2d554fa6c391faa88e4ff49775366b57","datavalue":{"value":{"entity-type":"item","numeric-id":2861557,"id":"Q2861557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bcba6a0dfc1a84d7c401e273dee13de46d15851","datavalue":{"value":{"amount":"+0.8403599858283997","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":"Q4632175$A7DF32DE-B99C-485E-B127-432696C7318A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1abd8065f458daff86293c66c513869394a0342d","datavalue":{"value":{"entity-type":"item","numeric-id":2942652,"id":"Q2942652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"490e744048d3b0ba090c6fd91935d901b9e21e11","datavalue":{"value":{"amount":"+0.8347718715667725","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":"Q4632175$697C2187-7E56-4CCB-A524-241A3CBBF93C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polynomial time algorithm for finding a spanning tree with maximum number of internal vertices on interval graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_polynomial_time_algorithm_for_finding_a_spanning_tree_with_maximum_number_of_internal_vertices_on_interval_graphs"}}}}}