{"entities":{"Q1174134":{"pageid":1184883,"ns":120,"title":"Item:Q1174134","lastrevid":46212940,"modified":"2025-12-24T08:05:47Z","type":"item","id":"Q1174134","labels":{"en":{"language":"en","value":"Unit disk graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8146"}},"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":"Q1174134$367C32B1-ECA2-4866-B2F8-5BD0B41C66FF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"34f6181672c998a8bcaf2b833069a4185ecceab4","datavalue":{"value":{"text":"Unit disk graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1174134$1930BFA4-B658-442C-B886-941DC2DB5877","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b5f191483bf456b7204eaca684a9c3d122233214","datavalue":{"value":"0739.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174134$CC1BFF09-31E1-45DE-B4AF-26E5E91E8D9A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"217c95f2f7d204dfd430a4376c72fca515a551fe","datavalue":{"value":"10.1016/0012-365X(90)90358-O","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174134$566D70A8-EFAF-47DA-ADD0-C73514D6F84B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"487d779fb1c997ca5ecf8ed0e05ea80f61c179d0","datavalue":{"value":{"entity-type":"item","numeric-id":1174133,"id":"Q1174133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$463A4628-274D-42C0-844C-FB28B78371CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbbdc3381c094a1abe2cf60ed445a4984b25837b","datavalue":{"value":{"entity-type":"item","numeric-id":168193,"id":"Q168193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$422537F8-99DC-4B97-9898-B3076ACFB995","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ecf2d8824396c280beb38bdd66733991f0508cba","datavalue":{"value":{"entity-type":"item","numeric-id":721935,"id":"Q721935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$AF91AD8B-4A34-4CC4-9837-80C99A82E95A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$5F9DD7D1-500B-4990-9250-5CEBB6EA38F0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1174134$5DFC9EB5-AEDC-4319-9165-789F558B06A5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c8da3dbc429bd25978de1db025591b5ae43a011e","datavalue":{"value":"Any given \\(n\\) points in the plane form the vertices of some graph by the convention that distinct points are adjacent whenever their distance is at most 2. The resulting graph is called a unit disk graph, since it is the intersection graph of the unit disks around the given \\(n\\) points.   It is shown that certain hard decision problems remain NP-complete when restricted to unit disk graphs, even when the position of the points is given. These problems are CHROMATIC NUMBER, INDEPENDENT SET, and several others.   On the other hand, a maximum cardinality clique in unit disk graphs can be found in polynomial time when the position of the points is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174134$F2C3A331-DACD-4D4F-A514-A2527D7C31E4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174134$7E357B3C-AEC7-411C-BD51-EF13C84C94CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174134$217C52EC-780A-4FAC-81C5-808ED925E788","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eddda12862d7e7f901e7a7b12a2a2908ddab07fc","datavalue":{"value":"8146","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174134$A04D8796-5D72-42F5-AA98-9F788F5A1177","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174134$32AF7818-A662-44F2-902C-7F10B2C6197D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"090ff11754306e0a299276715dbec01a1a1c5f5a","datavalue":{"value":"points in the plane","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174134$A9328050-1ED2-4FD3-8F66-9EADAEF402DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfa4ce6cfbd5e618995529bd1343a4a7f34072a4","datavalue":{"value":"unit disk graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174134$7C782EE6-9684-47E7-B4D8-54CD6B8B12B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bc0d5058cf7773f67ff6548c4fa33edb07db16a","datavalue":{"value":"intersection graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174134$BACDE4B5-BB55-43F3-9CF8-7831C80CCBE0","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"39e7b891292024efe7f3471ba50267381beab0f0","datavalue":{"value":"Q56210399","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174134$C41D4A6A-E5A0-42EC-9F3C-0680F95C5184","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0748e85c1b0f40a68146ca2556ec923bb53f58d4","datavalue":{"value":{"entity-type":"item","numeric-id":178604,"id":"Q178604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$1E5A7772-3EEE-4EF8-966D-544FA4710F94","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":"Q1174134$ADAB2BD3-AA08-4256-A68C-3E969FDBA41E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f380170dd9de5e69fb40eb46470ac085e19dc87a","datavalue":{"value":{"entity-type":"item","numeric-id":1174134,"id":"Q1174134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$9E6C5D2C-8C81-4B47-B1AA-3B669F3728ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5b18e5a44e3c67c75b0887be40e31fe6fc87d6","datavalue":{"value":{"entity-type":"item","numeric-id":4080986,"id":"Q4080986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$EBC35923-3B79-4FCC-9BB6-1F6BA0D91826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$7D1FA6CF-AD7D-4E8A-9899-49DCAD7406C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89a031afe32dfcbf4f8fba11966dba55c1408ae","datavalue":{"value":{"entity-type":"item","numeric-id":4179026,"id":"Q4179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$2F792A84-2BBE-434B-996C-FDA78516E98E","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":"Q1174134$503725BB-B6D9-422F-B8BE-8ABC460A1272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$DF2A2119-8E3F-4294-8C4F-87A0D29EE64A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fa97f0110ceefce3316c5fbe9c21778948ad688","datavalue":{"value":{"entity-type":"item","numeric-id":4742820,"id":"Q4742820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$F9B87E87-0FB1-4173-AE5B-403EFDC19FDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea967d3da9256d0a63f2da47bb550aa1eb20155b","datavalue":{"value":{"entity-type":"item","numeric-id":5905224,"id":"Q5905224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$77DEC7CB-703E-484A-A19E-F9B09094667D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0285625f074a48cd1908122f2f7d851fdd299e","datavalue":{"value":{"entity-type":"item","numeric-id":3747723,"id":"Q3747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$7ECFAF76-5FDC-4F86-BA53-1BE0A2F545A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c5200a3d79bea878bb3f1f1a63dd2799adadfaf","datavalue":{"value":{"entity-type":"item","numeric-id":5903516,"id":"Q5903516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$B6EEF35D-841E-4A45-92F2-94CD9E30419D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$4561B8E4-FAD0-403C-A199-90F9A612933A","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":"Q1174134$D4678754-7C08-44BE-AB10-AFA6369CABC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"886ba032e540aea708d21bd27fbc92799a765ca4","datavalue":{"value":{"entity-type":"item","numeric-id":3686754,"id":"Q3686754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$C0E2401D-1A07-4849-A354-21BC96AC83CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c54e28add7e2c1b5a8342b387f8dd0ff13edae6","datavalue":{"value":{"entity-type":"item","numeric-id":5630838,"id":"Q5630838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$12FDC50D-7706-4A2D-8BAF-A31BF7BD3B64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcc67d47bf3c27fbeab166391b3b3e9d154ed32f","datavalue":{"value":{"entity-type":"item","numeric-id":3904539,"id":"Q3904539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174134$5EA27605-D3E5-4927-B021-0CABA2E0F0AB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53d989ca6b57057f860821330b643655042561df","datavalue":{"value":{"entity-type":"item","numeric-id":1386337,"id":"Q1386337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18ee06d02f2ced7746d779bd044cedc427379f0c","datavalue":{"value":{"amount":"+0.8378729224205017","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":"Q1174134$1171E213-B481-42F8-A949-347050FA7B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b759b203d583d7af0115ce4fc4001b5f245bc583","datavalue":{"value":{"entity-type":"item","numeric-id":3095042,"id":"Q3095042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0502a763551de82762debc94116bc8bd5872222f","datavalue":{"value":{"amount":"+0.8324200510978699","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":"Q1174134$9407F2F4-ACCC-4AEE-B727-D3EC4021E5CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a5c3f6435b1538290444fb01296c1db128d786e","datavalue":{"value":{"entity-type":"item","numeric-id":1384186,"id":"Q1384186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7685b3479ccb2f1ab924fa2a6b80457477d9070f","datavalue":{"value":{"amount":"+0.8307477235794067","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":"Q1174134$19F22673-80B5-4945-A6E2-AB845268F730","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1174134","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1174134"}}}}}