{"entities":{"Q1074505":{"pageid":1085257,"ns":120,"title":"Item:Q1074505","lastrevid":69811641,"modified":"2026-04-13T09:33:22Z","type":"item","id":"Q1074505","labels":{"en":{"language":"en","value":"Generalized Steiner problem in outerplanar networks"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3948022"}},"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":"Q1074505$45C384DE-A1FD-4228-8C78-1E995F9C43DB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c9913755f9e2515262b88b4e10e5dc39e92b23db","datavalue":{"value":{"text":"Generalized Steiner problem in outerplanar networks","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1074505$B15DC6F0-2F89-40AB-BE11-EAC79348E95A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"91e7e4256a5df8fc5e1c2f592fb83ca8a60e47ec","datavalue":{"value":"0589.90081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1074505$45F343D6-CD18-4E48-80C5-5D7FA4CE7824","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0ac7a94b398055bac2fbdf46bde3fa6a0855d37e","datavalue":{"value":"10.1007/BF01935369","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1074505$AA3CC0F8-3752-48F6-8C95-2FB017AB5D7B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"489811fbf8c6d8c0740c5fbd21d01b77d56cfbb9","datavalue":{"value":{"entity-type":"item","numeric-id":583879,"id":"Q583879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1074505$CC6127B9-4739-4B23-B2A4-C67512CA9DD4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1074505$C6479DBC-6CA8-413F-BE3B-1C9CE77F2686","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1074505$77C27B3F-BCDB-4A77-AAB2-D63A50E6E28D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7d2cf36cb4b499dafe999a80c5d8ec8c6f653da4","datavalue":{"value":"The generalized Steiner problem in a network is considered. The generalization consists in the requirement that some vertices satisfy certain pairwise (vertex or edge) connectivity constraints. The general problem was known to be NP-complete, but for the case when the underlying network is outerplanar and the subnetwork is required to be biconnected (or edge biconnected), a linear time algorithm is presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1074505$E3E8D94D-5B2F-427E-A6F7-51F6C1526BBE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1074505$51F70DC8-6645-4D0E-9432-E85D726F66A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1074505$B4B4607D-9BAC-4D64-BFBC-DB3B35041378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1074505$26CE11BD-8EE1-4F4B-85F4-297DC92D267A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a8476d32696904268f581915420c7449791d4bfa","datavalue":{"value":"3948022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1074505$7B71CCEC-3ABE-4D07-8AD5-7631C2B659FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c133535e279b1c204dd003b0e961a47e8e47ca9","datavalue":{"value":"outerplanar network","type":"string"},"datatype":"string"},"type":"statement","id":"Q1074505$82631942-A03F-4AD9-A7B1-3EBAC0F071E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40b29151c19372952924bf28dcec8d7e764ef69d","datavalue":{"value":"generalized Steiner problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1074505$67B68667-948A-4D97-A90E-3B4E149B7FDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00d94580e507adc41bd69c5aefd7ceb60e931606","datavalue":{"value":"connectivity constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q1074505$23353D69-60C8-40FF-8980-A929691E8BBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1074505$4B390BFE-56DB-4C24-8AA1-4130D7618851","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"208fd2cac25388eac9d979aba68dad257ddb3873","datavalue":{"value":{"entity-type":"item","numeric-id":224835,"id":"Q224835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1074505$BA88921D-0467-4EDC-A34F-4060809491FB","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":"Q1074505$518698D7-64F1-4033-B58D-D691891ADC10","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1074505$A198C1E4-9655-4B8A-AD66-52DD370DF705","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dc218ab921b564879bcddff33adef4a824fbf89","datavalue":{"value":{"entity-type":"item","numeric-id":3048268,"id":"Q3048268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1074505$4E8784D4-2194-4B43-9380-D6F6C5AC25FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4be8f44328d07e3617361d570d4ffb07d2f5fbc2","datavalue":{"value":{"entity-type":"item","numeric-id":3929516,"id":"Q3929516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1074505$3AC9EF78-EE06-48F0-A34C-4D90751D6BA7","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":"Q1074505$829D5777-025C-44B1-842C-706FB6AFBC25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56cf648411a5f0ff052a98185ee5cbfaca5b8a8b","datavalue":{"value":{"entity-type":"item","numeric-id":5636922,"id":"Q5636922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1074505$08F29C6F-43A0-4E16-9F4F-42248174B8A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2c594e9705e780a6a4b2b01479e5d5553e79570","datavalue":{"value":{"entity-type":"item","numeric-id":5572939,"id":"Q5572939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1074505$064664FE-39F2-4AA5-B105-F6A69E13F5CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84c35c3c18100f10a76a9ef0d730325b542a65e7","datavalue":{"value":{"entity-type":"item","numeric-id":115238,"id":"Q115238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1074505$79905F11-5F6E-4006-A10F-701452922504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b8e8000a5c46af7f14f1ef902ca814ee5ae8991","datavalue":{"value":{"entity-type":"item","numeric-id":4179030,"id":"Q4179030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1074505$F8E43BE6-0798-4CFA-9258-DE736EEC303D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1074505$1A945E65-80A6-4C9B-BE1F-8522EBEDEA50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad9cfae9fc9d02b6b7648a5f38f2a07226c5c18d","datavalue":{"value":{"entity-type":"item","numeric-id":3311677,"id":"Q3311677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1074505$4FB1196F-E902-4860-8F90-E5C723562482","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"99d56cb67785dee927fdb7f99ad8918abbfb2e6f","datavalue":{"value":"https://doi.org/10.1007/bf01935369","type":"string"},"datatype":"url"},"type":"statement","id":"Q1074505$2B7DD657-AF7F-4A25-A94A-7206C5297D81","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c9f4c124fbcf74f7fb913bde8145e5ea9fd47841","datavalue":{"value":"W2050142375","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1074505$D42C08C1-0293-4051-AD94-B239B6C20E56","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2aef12e18065f1cc9583826e08a9d8198987bfa8","datavalue":{"value":{"entity-type":"item","numeric-id":3762228,"id":"Q3762228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a45198de16350aa761403ca7710bb5fa392faa09","datavalue":{"value":{"amount":"+0.8924990892410278","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":"Q1074505$71BA4880-1E73-4BF5-ABDA-6E0B1ACCC4F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd5798a23239847b9d708c3fc5de94ef6de9b5e4","datavalue":{"value":{"entity-type":"item","numeric-id":4842113,"id":"Q4842113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee2abd35e1e7de5a0ddd8b6f143346234747f4b5","datavalue":{"value":{"amount":"+0.8276114463806152","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":"Q1074505$0168AD98-435E-4D31-B7AD-5A33396D5215","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"332408bc45004d6330be2dddc9031cabdbf926a1","datavalue":{"value":{"entity-type":"item","numeric-id":1179749,"id":"Q1179749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f110f481183b0a32d03f7c50b220828371184eb4","datavalue":{"value":{"amount":"+0.8232677578926086","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":"Q1074505$54F83BBF-F3B5-4E53-9F23-0C85C5590E92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a465a5437f6a372fc7adbd896cf079b7fd9b1be","datavalue":{"value":{"entity-type":"item","numeric-id":3787806,"id":"Q3787806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"572870234bda8c088c226af23d47f54f4d337b68","datavalue":{"value":{"amount":"+0.8217950463294983","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":"Q1074505$2A698D3A-A70C-495D-94E4-9CACFF4302FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06245971b77e0d223b7fff6c3c9c0d4f78d0c3cf","datavalue":{"value":{"entity-type":"item","numeric-id":3060717,"id":"Q3060717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2c58dc3c6807e4cb4252d7ca7dc8ba43a07afe3","datavalue":{"value":{"amount":"+0.8161501884460449","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":"Q1074505$F82A0693-1520-4A1D-8126-4DA21C9DC116","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalized Steiner problem in outerplanar networks","badges":[]}}}}}