{"entities":{"Q685602":{"pageid":687451,"ns":120,"title":"Item:Q685602","lastrevid":78196259,"modified":"2026-05-06T11:01:04Z","type":"item","id":"Q685602","labels":{"en":{"language":"en","value":"One strike against the min-max degree triangulation problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417468"}},"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":"Q685602$BE9D168A-84B8-425A-A339-3CBCAB2CC9BB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d2e43bf0a44b806777f1848807cdbd3439cbb88c","datavalue":{"value":{"text":"One strike against the min-max degree triangulation problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685602$52D2174E-4A03-4644-976D-456557B52EA2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"54d8d54887e8a957f2b02307277516136f161649","datavalue":{"value":"0779.68088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685602$182449D4-3E02-41C5-ACC7-722EABFC9A24","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ce2200df823b7fd8848cebe9bb9793daeb2aadb5","datavalue":{"value":"10.1016/0925-7721(93)90003-O","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685602$B71EEC19-47F2-40B7-8FBC-A3EB622350CB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"38a47e2531a4bf8122b29daae2886484554c2a60","datavalue":{"value":{"entity-type":"item","numeric-id":243609,"id":"Q243609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685602$56F0C77C-8A2E-485C-B40D-4AC410B8BC09","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685602$C1DF29D5-7AE4-4FA4-9896-6ABE59883817","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ea9458ce3029a7f683c04e43e886fdc910ea299c","datavalue":{"value":{"time":"+1993-10-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685602$09C12426-20A0-4106-A2E0-1BB363F89E83","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4e9e2a21a59eac631444f5ab891893d27ab54e6c","datavalue":{"value":"The min-max degree triangulation problem is the following: Given a finite plane geometric graph \\(G\\) in \\(R^ 2\\), and an integer \\(k\\), is there a triangulation \\(G'\\) of \\(G\\) with maximum degree \\(\\leq k\\)? The author shows that this problem is NP-complete for \\(k\\leq 7\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q685602$5AE24D7F-B3EC-4013-866C-1280CA3FE647","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685602$9D6E1DDA-12DA-459C-A541-58B93AD974A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685602$FC2F07F4-BAC1-4D03-92AD-18BAAF94F4CD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c0c737ad838263a766837b6ed5bd4327f55fddfa","datavalue":{"value":"417468","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685602$293103B8-AD20-48C7-A3C9-30D6979E242D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bd3b97137fc5cddeb53bb49b8b441b42d47d65a","datavalue":{"value":"triangulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q685602$0BD0A819-403C-42C3-BE98-392FD52EB9BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0cd2bad7f8171f3265bcc7063cb3c4ccf853f203","datavalue":{"value":"geometric graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q685602$E18A9E53-2B73-4A9E-A458-747C3F5F5FC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q685602$33C86D1C-713A-4FFE-8BC7-D7B2FF17A7B4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f97401dc38cdab90e116741461a88db9a2626407","datavalue":{"value":{"entity-type":"item","numeric-id":701798,"id":"Q701798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685602$1ED29B76-52C7-4C9E-984B-93001E7A44D4","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":"Q685602$C30472DE-1533-4CE8-86EE-492F304A1EF2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bba877bad3c41b9bd83b05b4077430f58c551fd","datavalue":{"value":{"entity-type":"item","numeric-id":2368129,"id":"Q2368129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685602$75B2511D-59A1-45E2-9CBA-25F7A4173CA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02e306d21cf76cb92ce64aa5266ef8155ca76a92","datavalue":{"value":{"entity-type":"item","numeric-id":4030037,"id":"Q4030037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685602$BAAE3985-3239-48BD-9FF7-4D0A906DC296","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":"Q685602$A5916E05-E248-489C-B1EE-617CF619BF8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aac5c6d07e3cf99a9901c3d9a11ec1d6fe45604","datavalue":{"value":{"entity-type":"item","numeric-id":5056146,"id":"Q5056146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685602$F8A2F333-55CF-4EF0-AAE7-CBC7A08D2947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"176f92be0a5c8084cbea32a162c15c6e5a582bd9","datavalue":{"value":{"entity-type":"item","numeric-id":3936195,"id":"Q3936195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685602$27B0700B-0E1B-4868-8528-DCDDE13AC1D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af2dc51f455e8035861032dfb9491c0817f3e724","datavalue":{"value":{"entity-type":"item","numeric-id":1085168,"id":"Q1085168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685602$71ACDC19-99EE-49DF-9F0B-928F3F328BDF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"adad9a2ed761b858b31ed067d13ac7b4f855d26c","datavalue":{"value":{"entity-type":"item","numeric-id":5056146,"id":"Q5056146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aea47b12b08df155c9abeb2f097dc5ccd04176ca","datavalue":{"value":{"amount":"+0.8669000267982483","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":"Q685602$C84B8B7E-71F5-4B9C-BB47-F70F08C6D5E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56deb6dd9b603afc2479aaa92fe61161e97206de","datavalue":{"value":{"entity-type":"item","numeric-id":1363779,"id":"Q1363779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b85f322503fdb304f628233648322a44b18e480","datavalue":{"value":{"amount":"+0.8419461846351624","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":"Q685602$F83787E2-5C91-4F8A-8431-EF916BE09FB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a011e3bd9458506087053a219a0d8fb56db09c5","datavalue":{"value":{"entity-type":"item","numeric-id":3546362,"id":"Q3546362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ecdcbd10c334c85d8ba1f2bc490c60557a68b31","datavalue":{"value":{"amount":"+0.7834421992301941","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":"Q685602$248D348C-3209-464B-9F23-0036DEA9383B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c4fed6f5cf5a9ce9d205951579dce6a3696ea4f","datavalue":{"value":{"entity-type":"item","numeric-id":2708044,"id":"Q2708044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe583f59d44b8bd31aa9e635918942f2da419c41","datavalue":{"value":{"amount":"+0.7791174650192261","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":"Q685602$B4D6AA6D-0590-4BD8-AF13-68E05BFCB4A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f58a5039ab33ef3639ab83f001a1c018055102f2","datavalue":{"value":{"entity-type":"item","numeric-id":1343467,"id":"Q1343467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eebe24d2d3f540da9310369a84f0085890692b67","datavalue":{"value":{"amount":"+0.7770285606384277","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":"Q685602$D125717F-BF10-466D-BF89-E51690E577C2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"One strike against the min-max degree triangulation problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/One_strike_against_the_min-max_degree_triangulation_problem"}}}}}