{"entities":{"Q864131":{"pageid":865979,"ns":120,"title":"Item:Q864131","lastrevid":50026060,"modified":"2026-01-12T17:13:23Z","type":"item","id":"Q864131","labels":{"en":{"language":"en","value":"A generalization of the pentomino exclusion problem: dislocation of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5124962"}},"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":"Q864131$F00DEED8-D60C-4CC7-A05A-E15A5978598B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5102f840e7c90035a912ff67f6f060b509f96084","datavalue":{"value":{"text":"A generalization of the pentomino exclusion problem: dislocation of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q864131$E9D4E2AA-3E46-48FF-8FE6-BF6416E0C1B6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ebbda72106537dfc59befa1b7f94bcf87e010b4f","datavalue":{"value":"1112.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q864131$B491E9E5-78F9-4DE9-BCA5-AA98F29BD53A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"692ce2048991e39aaf8d5623dc50cd220956e79b","datavalue":{"value":{"entity-type":"item","numeric-id":189438,"id":"Q189438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q864131$8FF828AA-652C-4014-B961-06FA95CC5E1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb267048d3101ad8a827dae21aaf5fe8a1831b64","datavalue":{"value":{"entity-type":"item","numeric-id":442400,"id":"Q442400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q864131$EFF074E9-08BA-4DD0-9EBA-043B1BE099B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0312988617bd2777c13269ea03e8178d4db4bad4","datavalue":{"value":{"entity-type":"item","numeric-id":190528,"id":"Q190528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q864131$3F392AB4-D74B-4F4E-BA53-9952E75F37EB","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":"Q864131$45B9A925-E13C-4142-9AD2-06086AC1DBC2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6774d6ab22787c63fbf9dfb9bb080cedf0202a59","datavalue":{"value":{"time":"+2007-02-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q864131$F6F1A1D5-AE44-4E35-97F0-57E64AF7D3DF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"80ca3a74eb64a14f4027149bc2ca06e848d0fdde","datavalue":{"value":"A pattern formed by the connection of a specified number of equal-sized squares along common edges is called a polyomino, and if a polyomino is made up of five squares then it is called a pentomino. The concept of polyomino is due to Golomb who also proposed the following pentomino exclusion problem: Find the minimum number, denoted by \\(P(k,n)\\), of unit squares to be placed on a \\((k\\times n)\\) chessboard so as to exclude all pentominoes.   In this paper, this problem is solved for the \\((5\\times n)\\) grid and some upper and lower bounds are provided for the \\((k\\times n)\\) grid for all \\(k\\) and \\(n\\). The generalization of the problem to graphs, called the \\(\\Delta\\)-dislocation problem, amounts to finding the minimum number of vertices to be removed from a graph so that all the remaining connected components have cardinality at most \\(\\Delta\\). The algorithmic aspects of the \\(\\Delta\\)-dislocation problem is also discussed, and it is shown that the problem of calculating the value of \\(P(k,n)\\) has a solution with a running time, with \\(k\\) fixed, being polynomial in \\(n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q864131$20D00F3E-38C0-4063-BBD7-4D04452E0429","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c5966bacba611d16b7c796cf01c056e7b12d67d6","datavalue":{"value":{"entity-type":"item","numeric-id":607023,"id":"Q607023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q864131$DA78364E-5F0C-441E-82EB-B99CA7009F66","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"44858eee6702c5fd32430c310ff496cbf7eec374","datavalue":{"value":"05B50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q864131$37152C17-ED6B-401A-ACE9-501E97A90A06","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7a13c2f134fefaf012cde7cf7c08937483d98fb6","datavalue":{"value":"5124962","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q864131$3C471356-EFE8-43D5-AC99-903D6E40AF1B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c2f1187e6b36ac9f61bb736113a3cfeeec3cb32","datavalue":{"value":"fasciagraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q864131$E2460A97-6200-4795-86DF-35AA6347845C","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":"Q864131$8B6CFB36-7A3A-4BCC-B237-EC10FEE0F5C2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e2906224d7735fb81bbe7308a03e910726d63b38","datavalue":{"value":"https://doi.org/10.1016/j.disc.2005.09.036","type":"string"},"datatype":"url"},"type":"statement","id":"Q864131$E94630F2-C094-4599-AFA7-BA388EC5DDF2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f2045bc67b3119317eb98583dc775fc0bb005555","datavalue":{"value":"W2046145508","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q864131$91A47648-5864-4505-954A-CC44F6226159","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"842917a971b09105c7f7a79ed387d42a60c353dc","datavalue":{"value":{"entity-type":"item","numeric-id":4529658,"id":"Q4529658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q864131$BB32A1EE-82AC-4BDF-AEF9-6B370C868DE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b031bdbf61a477ed51940b99aa80dc940d2bae5b","datavalue":{"value":{"entity-type":"item","numeric-id":3903001,"id":"Q3903001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q864131$5F9EC020-2D31-479D-BF86-55CDFDD0B6A4","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":"Q864131$85AC52C4-F10C-49C6-9A65-E0596A3EBCC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad0283a9ec28c74b456a5bc2659f00d8c48dfd12","datavalue":{"value":{"entity-type":"item","numeric-id":4313096,"id":"Q4313096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q864131$39D2A050-0A63-4335-A297-4332BBE9A17A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85239715741e3948199dc66b583b1d5e10beece1","datavalue":{"value":{"entity-type":"item","numeric-id":5587625,"id":"Q5587625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q864131$B032366B-311F-4001-A0E8-BC6D0E4E6684","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e60a11fa67029a7c6a20d3a1b0590ea1c26faf05","datavalue":{"value":{"entity-type":"item","numeric-id":5953077,"id":"Q5953077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q864131$37622088-B673-4C77-958B-CF338B7D3CA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"582c9baed8ebf7e5a6269563114bd6608e1c0b91","datavalue":{"value":{"entity-type":"item","numeric-id":1917348,"id":"Q1917348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q864131$9441FBA6-A954-4317-A302-1D3400CD8716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f3d72d6f067eeebf02882fdf0a5f1edb3452f80","datavalue":{"value":{"entity-type":"item","numeric-id":1155513,"id":"Q1155513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q864131$3858D1CE-9AFA-4E65-981A-89427BBE7683","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2ef8974cd21e32f633d6004410a0740115594de6","datavalue":{"value":"10.1016/J.DISC.2005.09.036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q864131$44D04A7C-BE02-4D33-A20F-88683889D615","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8aff2173a3fb1e7b8a1e701cd1f1b12ae9c77619","datavalue":{"value":{"entity-type":"item","numeric-id":3412140,"id":"Q3412140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c19a297375778c5aae40928961f5c85b25bcb857","datavalue":{"value":{"amount":"+0.9399483799934388","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":"Q864131$0DE15858-FF09-46C2-A711-2F2DBFE92388","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19c6b4e8936eadda09261741787cea0a552ccac2","datavalue":{"value":{"entity-type":"item","numeric-id":5953077,"id":"Q5953077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc8c29ff40f099be17ac20fe163b7893f6c71961","datavalue":{"value":{"amount":"+0.7675844430923462","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":"Q864131$D41BB2C8-35C1-44F9-9A84-C16404973D43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f80a8d7b3489608b7e0cafb62a97a577af5f8c14","datavalue":{"value":{"entity-type":"item","numeric-id":624413,"id":"Q624413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc8c29ff40f099be17ac20fe163b7893f6c71961","datavalue":{"value":{"amount":"+0.7675844430923462","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":"Q864131$953146D0-F9C0-4C3D-9AD2-D6C45D121FF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aec21510fe1973538dad3eeece920e008cff99fc","datavalue":{"value":{"entity-type":"item","numeric-id":5431780,"id":"Q5431780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4573a05335b1be7d62f8e7d8b5ef879676038f2","datavalue":{"value":{"amount":"+0.7485283613204956","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":"Q864131$EAB4BD5C-14B2-4F3D-A1EB-FD6D5CE952B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"043835b86fea8a2c1c5a91c9bd64a4be9eae6958","datavalue":{"value":{"entity-type":"item","numeric-id":4461636,"id":"Q4461636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"133797ee63040e019161c671a59f4687f8db2b1a","datavalue":{"value":{"amount":"+0.6852574348449707","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":"Q864131$10631475-33C9-42D8-845F-97E9D20129E1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:864131","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:864131"}}}}}