{"entities":{"Q410643":{"pageid":412410,"ns":120,"title":"Item:Q410643","lastrevid":51442373,"modified":"2026-01-18T06:29:04Z","type":"item","id":"Q410643","labels":{"en":{"language":"en","value":"An efficient algorithm to solve the conditional covering problem on trapezoid graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6021215"}},"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":"Q410643$3E2CB1AB-7FE8-4112-A694-A220CF9B7458","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"80a406205e2d4b506046e25cd7d55f73a64baeb9","datavalue":{"value":{"text":"An efficient algorithm to solve the conditional covering problem on trapezoid graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q410643$2DB884AB-BE59-41FB-9FCB-7808104188D7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ada93e3ef88717919a5911b78b583051477afbe8","datavalue":{"value":"1238.05260","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q410643$43CB4A10-090C-4B00-87AB-428AE6A4728A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"65e2ba74615bd48126361fa39f1e95b72f1dc482","datavalue":{"value":"10.5402/2011/213084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q410643$B3B344CD-3A22-48CF-AFD6-55A00E92301E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"266c4bd2be60b49093a8f8e6c790014b33fc28c1","datavalue":{"value":{"entity-type":"item","numeric-id":410642,"id":"Q410642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$E1DCBA9F-9F23-47BC-8558-C8906EB3B0C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2097df7c97e7060602f45710b8b98fef7d97935b","datavalue":{"value":{"entity-type":"item","numeric-id":322052,"id":"Q322052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$89999B7C-DAE0-4723-B370-DE993DE9EBF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"129c1274b58ea0d36e8ffb4cb7701f96a7a7e865","datavalue":{"value":{"entity-type":"item","numeric-id":174580,"id":"Q174580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$0439F91E-18F1-4B48-90CA-4D462AFACDB4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"5e744686b6a66799a98d999a3cb7a2f5cc41f309","datavalue":{"value":{"entity-type":"item","numeric-id":410639,"id":"Q410639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$8B3C94DA-00CE-4DD5-B401-D32F88E63F65","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d567b51f320d6b206f1e246178a080db047a3948","datavalue":{"value":{"time":"+2012-04-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q410643$AADA9185-F050-481F-A11A-1549F352692F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d9005f1e0a3f46e9dc52e519e1c69be3441ffdd6","datavalue":{"value":"Summary: Let \\(G = (V, E)\\) be a simple connected undirected graph. Each vertex \\(v \\in V\\) has a cost \\(c(v)\\) and provides a positive coverage radius \\(R(v)\\). A distance \\(d_{uv}\\) is associated with each edge \\(\\{u, v\\} \\in E\\), and \\(d(u, v)\\) is the shortest distance between every pair of vertices \\(u, v \\in V\\). A vertex \\(v\\) can cover all vertices that lie within the distance \\(R(v)\\), except the vertex itself. The conditional covering problem is to minimize the sum of the costs required to cover all the vertices in \\(G\\). This problem is NP-complete for general graphs, even it remains NP-complete for chordal graphs. In this paper, an \\(O(n^2)\\) time algorithm to solve a special case of the problem in a trapezoid graph is proposed, where \\(n\\) is the number of vertices of the graph. In this special case, \\(d_{uv} = 1\\) for every edge \\(\\{u, v\\} \\in E, c(v) = c\\) for every \\(v \\in V(G)\\), and \\(R(v) = R\\), an integer >1, for every \\(v \\in V(G)\\). A new data structure on trapezoid graphs is used to solve the problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q410643$A61B0843-96D6-4777-B12C-FF95A4ED0349","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q410643$D8C1CC5A-B897-4015-9BA0-92D88A5B6D1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q410643$13B8A650-DD44-4B4F-8249-2E0EE295A83C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb6fa31c061028a10fb1c2a1679af7746583c504","datavalue":{"value":"05B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q410643$F0F2689E-2DAC-4CA9-A0B3-B1B173022FA3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"99da1bcd5c1292b985e6d1576a4cbc246b53334b","datavalue":{"value":"6021215","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q410643$2F7FD782-2A8B-402B-AEA3-5B8B2FA51D2A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"953154a60cc39a436dacdba9f9a51f06e3011458","datavalue":{"value":"data structure on trapezoid graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q410643$2A777045-3103-452E-9904-BB5EE38698CE","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":"Q410643$B590A5D3-DF51-48AE-9478-F433726329BB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"10c9d633bfe011bdf3bdf5ead3a811a1b4421a6e","datavalue":{"value":"https://doi.org/10.5402/2011/213084","type":"string"},"datatype":"url"},"type":"statement","id":"Q410643$757C00AC-0D16-436A-BB50-85FDAC5096F0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"36b1099c3d10658eabe2bd7a3d79794a0fa9a593","datavalue":{"value":"W2155274708","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q410643$6D83D369-BFFE-4B68-B59F-61DF53CCEF10","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"4b52edce00e8de0aa026f326652db249cb5a3863","datavalue":{"value":"Q58689078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q410643$6AB1C382-420B-4807-8EB1-9FC0BF430AF8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88eb8dffac6e0208b811665c9650729429159d30","datavalue":{"value":{"entity-type":"item","numeric-id":5717712,"id":"Q5717712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$26FC3191-B967-468E-81D1-CAAA7356CB77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9eb051f9de617cd276e0ce7b24c6faedc6c1b50","datavalue":{"value":{"entity-type":"item","numeric-id":3797233,"id":"Q3797233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$A23F3BAF-E0A7-4AE3-90B7-5783F9EDAC2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79cc333a398e9d6212f316ca27b812994cbe7ce9","datavalue":{"value":{"entity-type":"item","numeric-id":1111577,"id":"Q1111577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$41333B7C-67C6-4A21-92C8-9FA436B49D42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d1ceb47e53781f62df58b5caae3f3f61154e16f","datavalue":{"value":{"entity-type":"item","numeric-id":1917308,"id":"Q1917308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$3F8ECFF6-AA97-43CE-9FDE-7EAFC465256A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bd3470bd13e171c6f0d323ba7e9b2134ff45fd8","datavalue":{"value":{"entity-type":"item","numeric-id":4312224,"id":"Q4312224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$3C91B1E7-DE6F-4388-86E5-121EE1B49780","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03c0b4343b244900f34366dd04710f4b0156908d","datavalue":{"value":{"entity-type":"item","numeric-id":3216395,"id":"Q3216395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$94B06466-3C17-4A5B-AA1B-C6FC7EED566C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36e6883852c73e6c253082e457c001e243ada4e6","datavalue":{"value":{"entity-type":"item","numeric-id":2365766,"id":"Q2365766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$A9B82BAC-074D-480F-8E73-84D6B86097FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6a69fba87496bcae7d2aae6711ddc8d8261905a","datavalue":{"value":{"entity-type":"item","numeric-id":1091265,"id":"Q1091265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$430789E2-D699-49E8-86C3-186620E63303","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10f64268c63bc593c7d1819d8bda3054465826aa","datavalue":{"value":{"entity-type":"item","numeric-id":1919972,"id":"Q1919972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$AA834C80-5F58-4CB3-B092-92A9A24842BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21b780dc71ac646e0dc7374775264a183f4362c4","datavalue":{"value":{"entity-type":"item","numeric-id":5717713,"id":"Q5717713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$2B8A917C-1790-4FF5-9449-569A3D24FE7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d3d8de957e948db8933512fae907c76cab89fc8","datavalue":{"value":{"entity-type":"item","numeric-id":4680424,"id":"Q4680424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$DC8AE324-71C6-44F8-8BE7-12AADB5DD471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee7cd02919845057a9d72d8dfcd746c3d6158fbd","datavalue":{"value":{"entity-type":"item","numeric-id":626967,"id":"Q626967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$DB95540D-CC32-4124-AAA8-D6CC8AF4885A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dda8c53f874957694ba2ba205c3859602e49f22","datavalue":{"value":{"entity-type":"item","numeric-id":3171770,"id":"Q3171770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$B0C41425-0B1D-45B8-B42E-910747702AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12ef4af0a65b06198ec697e6d886c27f5a70ee23","datavalue":{"value":{"entity-type":"item","numeric-id":2569405,"id":"Q2569405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q410643$E11093E3-A919-46F5-B04E-FF08301A9E4C","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":"Q410643$45BCAF37-D787-44D2-B276-5D7003BE5580","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"885a4d652563da91a5cd62f5519ae382dd929fe9","datavalue":{"value":{"entity-type":"item","numeric-id":3104274,"id":"Q3104274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8517533f8666cbb151036204fac5ccb81fd15012","datavalue":{"value":{"amount":"+0.8327971696853638","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":"Q410643$8C0B0C10-003A-40BD-B846-698F23BE1C1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2576262e40cd2b65351611a501b36c5cf3d3fd8c","datavalue":{"value":{"entity-type":"item","numeric-id":3100107,"id":"Q3100107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32f47230356ced471f77264d6eb307494e99eae3","datavalue":{"value":{"amount":"+0.8321424126625061","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":"Q410643$35D66AE1-4D07-4086-84CC-EA672D145E39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe9dfe3bce5c3509a84d886b07d9a98d42317f6c","datavalue":{"value":{"entity-type":"item","numeric-id":626967,"id":"Q626967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a16c80d1f4dbab51015e6adcdf41d8e9ec1a6d2","datavalue":{"value":{"amount":"+0.831633985042572","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":"Q410643$3001A6CB-D83E-4376-AD63-0B3EEF7836E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9e1225e6a3a24fe2fdee2fac43fa03cde6d7f17","datavalue":{"value":{"entity-type":"item","numeric-id":1948610,"id":"Q1948610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"698d5a3caa8ccf83213a975c9dae9ff51d41f2db","datavalue":{"value":{"amount":"+0.8288880586624146","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":"Q410643$73758009-F06D-4D72-A4C6-6B77A71F84D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9a27463a5c6276aa55c902575121036aafa7f3a","datavalue":{"value":{"entity-type":"item","numeric-id":4680424,"id":"Q4680424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f510f293bc02e7024ad8a4e5c0011b136088c4c","datavalue":{"value":{"amount":"+0.8151471614837646","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":"Q410643$E86C72CA-4889-4E2E-BC98-719364B79A51","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:410643","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:410643"}}}}}