{"entities":{"Q1720833":{"pageid":1731574,"ns":120,"title":"Item:Q1720833","lastrevid":57253593,"modified":"2026-03-27T16:09:01Z","type":"item","id":"Q1720833","labels":{"en":{"language":"en","value":"An efficient heuristic algorithm for solving connected vertex cover problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7018890"}},"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":"Q1720833$B8778BFB-9DDB-4E6F-9154-191DB84DB377","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c6a6ef8d077034988fe48e5731ea20e9d98af274","datavalue":{"value":{"text":"An efficient heuristic algorithm for solving connected vertex cover problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1720833$88E6B6FF-7162-45B5-B524-776AE270EBEC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a0d2f186df4cc835aa7bbd05b093bb44a1a251a8","datavalue":{"value":"1427.90305","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720833$876E990E-865B-4A14-896E-7D81F00975AF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3f6d129edf407f2481d3a338b532713e21537da2","datavalue":{"value":"10.1155/2018/3935804","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720833$86A09DE7-56E9-4D56-9EF9-481D7CA61A3C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"775028b4f1a7964092fb0f8546dc0d9af6162625","datavalue":{"value":{"entity-type":"item","numeric-id":1720832,"id":"Q1720832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$C805377C-95DB-4B37-B586-3BA89436A6F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4fe777bc8f1a12b03edb3e19dcaf175ba9d3caf6","datavalue":{"value":{"entity-type":"item","numeric-id":263123,"id":"Q263123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$47E7FACE-E55D-42F6-A033-63894AFC6F4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae4b1f8bbdb074514908d792984655f21bbe00f0","datavalue":{"value":{"entity-type":"item","numeric-id":185444,"id":"Q185444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$C10FB898-9A5F-47A3-B8FA-E2227EDA8122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9fe4085960916936e2fd7a18a6fa3560a35aed1f","datavalue":{"value":{"entity-type":"item","numeric-id":474509,"id":"Q474509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$2CC3E51C-2964-42FE-8114-6CDC5C0BA515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"548ee01e6e2557dd86cf6bf3cb9bb8e81c8401fd","datavalue":{"value":{"entity-type":"item","numeric-id":247886,"id":"Q247886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$6C52A970-7DFE-4923-A55D-E11AFE5EA968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1de4b9669ff9ade18e8990ed95ecf6b171debf52","datavalue":{"value":{"entity-type":"item","numeric-id":939827,"id":"Q939827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$F0A2B81B-90A2-4EB9-8DDE-9FF1D3C8CE03","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc97bc0aff607b9c22ce37ffa18b6de85001d90","datavalue":{"value":{"entity-type":"item","numeric-id":86199,"id":"Q86199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$77628C74-6215-480A-A3B2-3556B473A3F6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"32a6dc046c0aa99508538df457dbadf7aa620337","datavalue":{"value":{"time":"+2019-02-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1720833$998FB888-CE80-4399-9B60-D221EC864778","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ee01ec5aae4f12ef45d5708e378e8fe5960070ca","datavalue":{"value":"Summary: The connected vertex cover \\((C V C)\\) problem, which has many important applications, is a variant of the vertex cover problem, such as wireless network design, routing, and wavelength assignment problem. A good algorithm for the problem can help us improve engineering efficiency, cost savings, and resources consumption in industrial applications. In this work, we present an efficient algorithm GRASP-CVC (Greedy Randomized Adaptive Search Procedure for Connected Vertex Cover) for \\(C V C\\) in general graphs. The algorithm has two main phases, i.e., construction phase and local search phase. In the construction phase, to construct a high quality feasible initial solution, we design a greedy function and a restricted candidate list. In the local search phase, the configuration checking strategy is adopted to decrease the cycling problem. The experimental results demonstrate that GRASP-CVC is better than other comparison algorithms in terms of effectivity and efficiency.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1720833$A810C915-10A1-4EB8-A714-F4F58F0929FD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720833$52660712-35F0-4A1F-857A-FEA2B7467179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720833$CF627CCB-A410-4DC4-B0B1-BECAB51279D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720833$3B75BE38-C7C3-4A7A-ABAB-F3F2B29D3218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720833$DC0FE93B-B0B5-4FAB-98E9-9236F993E512","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"938b5148bf41dcac05de31b2bcf35b2ac1aac4f2","datavalue":{"value":"7018890","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720833$EEA69C10-5D62-47EA-BFF1-6D93E377DCFD","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"4e558e78bf7ae5246d1675f3a0fe05cd8c96cb94","datavalue":{"value":{"entity-type":"item","numeric-id":51751,"id":"Q51751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$19DB9B52-E96F-4056-9816-3C094A217161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"7daf7ec166de12a4dde35cdf00f90e35db7776c0","datavalue":{"value":{"entity-type":"item","numeric-id":20229,"id":"Q20229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$D40A152D-B2A2-4D78-8976-8BC96D635C76","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":"Q1720833$A5665882-DA58-4323-9205-DCF6F90036E5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7f6e1a7bbf8f37857ef069c10b144cdbb9ff0440","datavalue":{"value":"https://doi.org/10.1155/2018/3935804","type":"string"},"datatype":"url"},"type":"statement","id":"Q1720833$8945E088-642B-499B-8991-0335CFA643DB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c1d40d3678fd855c6c0499fd4c5370d9ec8f8d29","datavalue":{"value":"W2889606199","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720833$BD3F2EE3-88F8-441D-87E5-6B431DDA59BD","rank":"normal"}],"P223":[{"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":"Q1720833$827FDAAB-899B-45ED-989B-20DD6B56D333","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"233f5e9af8b09e0add8e21ff56cd4e6d29666ec4","datavalue":{"value":{"entity-type":"item","numeric-id":1040582,"id":"Q1040582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$FF44CD6F-04AA-45FE-924B-F27DC4BF933E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"facf567827fa94ce7ff4894d2d2de3550667b2e8","datavalue":{"value":{"entity-type":"item","numeric-id":1026225,"id":"Q1026225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$383341D6-0AB0-48B9-A3AB-6D10C30AD9E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9fca953ad089dbe8248c398ced285fb27086ceb","datavalue":{"value":{"entity-type":"item","numeric-id":929296,"id":"Q929296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$4669273E-4EEC-40C8-91ED-9FA35121A08E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0669e594826b5b3523dfa03abf605c0d6353cb8a","datavalue":{"value":{"entity-type":"item","numeric-id":1171390,"id":"Q1171390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$95398C56-F5BE-4D14-B790-9FB73D10BF9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"940388013ff2388798679711a9b00ae32f7a0326","datavalue":{"value":{"entity-type":"item","numeric-id":2390219,"id":"Q2390219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$42BA07F6-E82D-4BF7-A114-7F0508451C54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"072a036d40c19374e6e15cb6d627acaf3d5ccff9","datavalue":{"value":{"entity-type":"item","numeric-id":2266936,"id":"Q2266936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$459D9274-5C84-4128-92EF-A9581CE5B620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"923345f1e34904398a5f48b04a957b74c1093718","datavalue":{"value":{"entity-type":"item","numeric-id":3541785,"id":"Q3541785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$0B365E08-18A9-41D3-8DC7-048DD08194A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9591e87b5ff726c26d3ae1239ac062fdf22d9f90","datavalue":{"value":{"entity-type":"item","numeric-id":1735245,"id":"Q1735245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$5513163C-F680-4324-A3DF-559E81F61D71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b40a94a5f9eeea933b992fbb8342e3c42af085d9","datavalue":{"value":{"entity-type":"item","numeric-id":3186644,"id":"Q3186644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$B41F0972-014F-414A-BAC8-4669B5955F10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"984dcc667dee0aa6d4c178b9445c3f9dbf39883d","datavalue":{"value":{"entity-type":"item","numeric-id":4601636,"id":"Q4601636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$B008CE48-9F49-4EA8-A3A6-67B3EFE33641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d5c843166377c42a2a7c16df5c93d8199ec2f8e","datavalue":{"value":{"entity-type":"item","numeric-id":646517,"id":"Q646517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$02874856-2A68-44C1-B0F6-9104095151AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b56eb7553d40e29ba20c401fa27988e78d6fbe80","datavalue":{"value":{"entity-type":"item","numeric-id":2982183,"id":"Q2982183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$9F57273F-CC69-4D4B-B8E3-441CBFAE55B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8770cb49225be2c960a3f579d3509545fc60b382","datavalue":{"value":{"entity-type":"item","numeric-id":4917618,"id":"Q4917618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$4ECF30BB-A9C4-44F5-B3E4-6E32D2AB989D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7de69208b4e3d4582b72d563d541a50b36e7e85","datavalue":{"value":{"entity-type":"item","numeric-id":2424831,"id":"Q2424831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5443bf98af7eda3bfe08aa699dd78b85fae0aeea","datavalue":{"value":{"amount":"+0.7938516139984131","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":"Q1720833$4B3C2E35-7813-4903-B790-572BF7EFB41D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c7aa2bb28cade8391f00d6d8d3155ff5661f166","datavalue":{"value":{"entity-type":"item","numeric-id":5420473,"id":"Q5420473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"253b4302bcec7f5bc76e1c1f31b1b41975aca1a1","datavalue":{"value":{"amount":"+0.7917416095733643","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":"Q1720833$1D9F94A3-17A1-44E8-9442-8F8E977F4366","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96d3e47240d3388f5c6905d0d1af723e52e63b82","datavalue":{"value":{"entity-type":"item","numeric-id":5505664,"id":"Q5505664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bac1ddd4352909ab9d2d141ec7ad48edcf05652e","datavalue":{"value":{"amount":"+0.7858989238739014","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":"Q1720833$034C878E-EC6F-48EA-B204-46900A9956EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"211a98105a61905d5dea3bc448b3d65606e13c5d","datavalue":{"value":{"entity-type":"item","numeric-id":1735245,"id":"Q1735245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92e860700f95e691ac3abbf419d80bd6d0ebd8a2","datavalue":{"value":{"amount":"+0.7813034057617188","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":"Q1720833$905023D2-0845-47EE-B9E3-11EDF1F66AF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a290735b255e76da42ec9b4e29f9e17c9d957b0","datavalue":{"value":{"entity-type":"item","numeric-id":3976603,"id":"Q3976603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4a715ca3d1c239bb668e27632ff3982690137ae","datavalue":{"value":{"amount":"+0.7802759408950806","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":"Q1720833$6B279AD8-9EF8-40A7-8F3A-70F667E9D56D","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720833$68A98CC7-F5EF-4E8C-9763-31E489A14ED9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1720833","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1720833"}}}}}