{"entities":{"Q1789891":{"pageid":1800633,"ns":120,"title":"Item:Q1789891","lastrevid":68959767,"modified":"2026-04-13T03:22:39Z","type":"item","id":"Q1789891","labels":{"en":{"language":"en","value":"Solving vertex cover problem using DNA tile assembly model"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6950654"}},"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":"Q1789891$6D09162F-599D-4DE4-B25B-8E0476624B6D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9170396f325a401909b5013d566ad287a7c6f3f8","datavalue":{"value":{"text":"Solving vertex cover problem using DNA tile assembly model","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1789891$FFCF78DD-14CA-4781-8152-D3F73A09B1BA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cbb413fc0825fd0915297229c25ad374fbeea9e6","datavalue":{"value":"1397.68075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789891$090CE530-643A-4ED1-B24B-CE5CC479510C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3aeba59ea62a33d4035c5db9534ab9c9aace8b52","datavalue":{"value":"10.1155/2013/407816","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789891$BDE08D6C-1241-4C91-9701-12D4F6A92208","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b7a91d46ab14e3a6a58e3d832f71e55e0583dfe1","datavalue":{"value":{"entity-type":"item","numeric-id":391184,"id":"Q391184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789891$3E93A5B0-2646-423F-B969-2F28F35CF87D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3227e7c136fd6904de8b90a1efcdf78c6dd10b61","datavalue":{"value":{"entity-type":"item","numeric-id":1669996,"id":"Q1669996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789891$71C9B2B9-AFC8-4AB8-BAAA-FE71C880C69F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3af92a8bd5ac2c159593a7527f4fe9337f5adfd3","datavalue":{"value":{"entity-type":"item","numeric-id":1003589,"id":"Q1003589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789891$81185A7B-0080-4453-9114-EB4351D55EFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"52788f3974950723058685c1201b7828b0f68475","datavalue":{"value":{"entity-type":"item","numeric-id":943485,"id":"Q943485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789891$DE00884E-0EF7-4096-962F-216015A1D36B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"bb299feb2b87699ac8beef494c52fd2765eaf609","datavalue":{"value":{"entity-type":"item","numeric-id":118601,"id":"Q118601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1789891$6F398FD9-AB2B-4480-AB9B-D0196436F588","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9a9a21eafa993b72759052108b216b22ca406dd9","datavalue":{"value":{"time":"+2018-10-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1789891$3D67EDF1-C1AD-4472-A4D4-F6E5F1AA87FF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fe902cca89da2e919ab35587a347bf1fa31e5195","datavalue":{"value":"Summary: DNA tile assembly models are a class of mathematically distributed and parallel biocomputing models in DNA tiles. In previous works, tile assembly models have been proved be Turing-universal; that is, the system can do what Turing machine can do. In this paper, we use tile systems to solve computational hard problem. Mathematically, we construct three tile subsystems, which can be combined together to solve vertex cover problem. As a result, each of the proposed tile subsystems consists of \\(\\Theta(1)\\) types of tiles, and the assembly process is executed in a parallel way (like DNA's biological function in cells); thus the systems can generate the solution of the problem in linear time with respect to the size of the graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1789891$95831DBF-45CE-45F6-BD70-13143BE5BE2C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789891$65ED2406-A550-4BF6-AB58-E2D427C12A2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789891$EEAE7015-C2BF-4317-95BE-F92034FFEA7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789891$B3C2CBA3-F427-4FE6-AA06-6CB8CDBF43CD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a8b5db968da48e1c979fa42fc03d99cc5ce1bc29","datavalue":{"value":"6950654","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789891$C53FD0FD-247A-4381-848A-BD7C2F3C229C","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":"Q1789891$AE2B972C-B2BB-418B-A1C9-2B8803CB8658","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"15135d4fdf16541ce4fedba465142f38968b165e","datavalue":{"value":"https://doi.org/10.1155/2013/407816","type":"string"},"datatype":"url"},"type":"statement","id":"Q1789891$83A447B8-D1F8-4DA4-A375-75346D8D84A0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0216fe9628be72e21f2d87cc4a23b686f8ecae17","datavalue":{"value":"W2085910738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789891$13A2F55A-9AE7-4F4A-9CFA-9B7787174E36","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"734c1f515e916240f49639b2092c5d90de93ef13","datavalue":{"value":"Q59005798","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1789891$A125A4AE-5BD4-4BA1-8A54-7EDD9217419B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b19acaeaf1593debf2dbcc3bfcc0fa6563ba4aac","datavalue":{"value":{"entity-type":"item","numeric-id":924678,"id":"Q924678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a80c65618ba3a8c6793b61bedc10faf93d0969cd","datavalue":{"value":{"amount":"+0.7890418767929077","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":"Q1789891$B4EC52F3-471F-4EDE-A1C1-029CE668600D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c2e502ca3d052647c6fea1e8050facd7a587149","datavalue":{"value":{"entity-type":"item","numeric-id":5452688,"id":"Q5452688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15f0961acc1dbc36432c6645b6bd2410bfca2851","datavalue":{"value":{"amount":"+0.7871155738830566","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":"Q1789891$49B2F491-D30A-4059-8758-3FB61C7DBB7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03de050c8bbac9c8fa04c36a04d0f63a57870874","datavalue":{"value":{"entity-type":"item","numeric-id":3070958,"id":"Q3070958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d78e6ecdba9233d07fe8f43bbdac71b268b0c89","datavalue":{"value":{"amount":"+0.7843437194824219","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":"Q1789891$B488C086-A873-4D0B-97F6-C0921B5C2D49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"447822a2e1b7f1c8a6341993e85ade5b9be362d3","datavalue":{"value":{"entity-type":"item","numeric-id":3543477,"id":"Q3543477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f073d409ac741bd4afa72b0a2eb03975dc2ad0be","datavalue":{"value":{"amount":"+0.7803545594215393","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":"Q1789891$A5A5285B-FD4F-40EF-9B41-B79D1A0C7E49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2931fcaf5cd4508271508fbd5c980683bcb62fe9","datavalue":{"value":{"entity-type":"item","numeric-id":4529976,"id":"Q4529976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ac26fa68989be15d5cedbde22405ae631c7131d","datavalue":{"value":{"amount":"+0.7787659764289856","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":"Q1789891$B316445F-31D7-414B-9957-067B5B124C3B","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":"Q1789891$6278840E-99AE-4174-874D-5A41F804E6CB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Solving vertex cover problem using DNA tile assembly model","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Solving_vertex_cover_problem_using_DNA_tile_assembly_model"}}}}}