{"entities":{"Q1801670":{"pageid":1812412,"ns":120,"title":"Item:Q1801670","lastrevid":71291439,"modified":"2026-04-13T21:15:02Z","type":"item","id":"Q1801670","labels":{"en":{"language":"en","value":"On the complexity of the embedding problem for hypercube related graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 205576"}},"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":"Q1801670$2A7B10B9-700A-4A76-ACBA-B41D3B9DD8CA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"12690298f26905d97016638b0de3d1f2ec9e5bae","datavalue":{"value":{"text":"On the complexity of the embedding problem for hypercube related graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1801670$F65085F0-0065-49CA-97B0-E468B8383E41","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8463a147b62d87958c618a3c595bb437e6d2b999","datavalue":{"value":"0777.68051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801670$72A5CA44-3DBA-4662-B5EC-40DED4550CDA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a44566db106927523c459388ecbb7418a123c575","datavalue":{"value":"10.1016/0166-218X(93)90170-S","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801670$5A7DA201-7AC0-4077-A151-02BD8B01BAF4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$7657D9D5-28F6-43FE-8E49-1FA5DBF2B689","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"92112234a474f78049341bfb55637019f67e54ac","datavalue":{"value":{"time":"+1993-12-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1801670$B9378633-D69F-4FAA-8DCE-A169E2A94AE6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a15921519d249618a7014ca543fea07a03ff405a","datavalue":{"value":"An important family of graphs is the \\(n\\)-dimensional hypercube, the graph with \\(2^ n\\) nodes labelled \\(0,1,\\dots,2^ n-1\\) and an edge joining two nodes whenever their binary representation differs in a single coordinate. The problem of deciding if a given source graph is a partial subgraph of an \\(n\\)-dimensional cube has recently been shown to be NP- complete.   We illustrate a reduction technique used to obtain NP-completeness results for a variety of hypercube related graphs. We consider the subgraph isomorhism problem on two related families of guest graphs, the dilation two hypercubes and generalized hypercubes. We show that the embedding problem for both of these problems is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801670$21C8D515-DEAA-48C4-BA3B-E270F9232DF2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801670$DFFFC7BA-5FAB-4BC1-934F-B31610DC3AA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801670$2621FD90-6A97-4649-9765-CF340A3CFFDB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"82d2257b51586b74fc458fe467729fcbbdcaa3a6","datavalue":{"value":"205576","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801670$C8117031-ED1D-43E3-8755-4FBD295C16D3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da5857f76acc4c6e422115b9b8c49fc730f7f62b","datavalue":{"value":"multiprocessor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801670$AF84C443-C376-43F5-9768-83E2F562CAE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba9992e11c5a892ccd97460fbc31ceefeeb8b95d","datavalue":{"value":"graph embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801670$C9F00A0B-92BD-4337-B082-D88EB607F17B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801670$05AE62F0-41DF-4766-B8A3-E8D406FD9373","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801670$F79F61A8-85B5-4654-9D6C-90475D99ACCC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c145ed40ffcabf573ccc0e287afc84e81635ce77","datavalue":{"value":{"entity-type":"item","numeric-id":1309232,"id":"Q1309232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$15151126-A264-49B5-ABAC-512DD8182151","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eac3bc3b952de30e0dbd044a5b978d4bbca81a36","datavalue":{"value":{"entity-type":"item","numeric-id":1070246,"id":"Q1070246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$99849397-0F97-420B-B2DC-681A38CBD980","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cd676a67aa722f529c2cfce70849eee162745971","datavalue":{"value":{"entity-type":"item","numeric-id":1068928,"id":"Q1068928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$AA324E71-E5ED-4562-BB7E-631E26CED8FE","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":"Q1801670$443F8727-304C-4553-9A46-F67073E57588","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0db49ec9192280fc7f508364bb9f12bf7354f9a9","datavalue":{"value":{"entity-type":"item","numeric-id":3736911,"id":"Q3736911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$347DF2A1-F278-4F9F-9CC7-DF0DE24CFC3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c7e9f23d40e486f3e0667a10b0cbe69f7c5a63c","datavalue":{"value":{"entity-type":"item","numeric-id":3309028,"id":"Q3309028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$C7F92685-6AC2-42B4-B594-EC69AEE7AD34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"609ef23e119807fd2656f398d1eb03abc1f00f3c","datavalue":{"value":{"entity-type":"item","numeric-id":1108043,"id":"Q1108043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$707019AD-67CC-49D4-BF28-E40EDCAC1956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2436afecea717d449f669935f2d48c064b2aa71","datavalue":{"value":{"entity-type":"item","numeric-id":2555084,"id":"Q2555084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$BC597270-9881-41CC-B266-C147AEB0A2FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d111ed39e76e06afda08706f554c998997c48f2","datavalue":{"value":{"entity-type":"item","numeric-id":4710541,"id":"Q4710541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$0F7F960A-6303-4830-B48D-3398F3FD621F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5e21a0d2f846c7b5db53c68e1a2923e4c158d6a","datavalue":{"value":{"entity-type":"item","numeric-id":1067411,"id":"Q1067411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$9F9F67D2-102C-4C6F-A79B-5CBF7BA711FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"994d3cd3acdc76788b239889d1a0703e4babac68","datavalue":{"value":{"entity-type":"item","numeric-id":1215634,"id":"Q1215634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$A977F331-3A7F-4FA9-89CA-48154D8AFAB1","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":"Q1801670$F47A1A8C-DAA5-4E34-82E2-3EBBBB699093","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"331f46b5628ed6962f89bfe766c17c01f92fdf95","datavalue":{"value":{"entity-type":"item","numeric-id":3041106,"id":"Q3041106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$112119CB-FDE8-487A-81EF-BFF66CC5C1C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$C2A1CCF9-8316-4D77-ABF6-878927977E6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89ed82c569b09b2beaf6b802c6c308bb814b7161","datavalue":{"value":{"entity-type":"item","numeric-id":5659587,"id":"Q5659587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$5FA532CF-5A05-4F9D-973D-A3E02DE7EC53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ef1a7e5bdf6f66bdf28494a71f45a2af43da368","datavalue":{"value":{"entity-type":"item","numeric-id":1309233,"id":"Q1309233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$50E17278-021B-4B3B-B393-C365C8E823EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28f435e5a25fa982df62d6d5dae64d6c592f1a23","datavalue":{"value":{"entity-type":"item","numeric-id":3476279,"id":"Q3476279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$99EA1226-9B98-4155-AA96-B891569D7636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30ee28d0ed23e167ceb3fdd62454860bee3279de","datavalue":{"value":{"entity-type":"item","numeric-id":579285,"id":"Q579285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801670$546A80B1-8EB7-47AC-8A13-1FAF31E7881B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0d56845a823ece19a85aca717518cefdce722058","datavalue":{"value":"https://doi.org/10.1016/0166-218x(93)90170-s","type":"string"},"datatype":"url"},"type":"statement","id":"Q1801670$DE5A2F17-7DCE-4C59-BB95-569DD42DD9DC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"05fba0a495f74e13597a1482c1f969eaa03fed4e","datavalue":{"value":"W2074222994","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801670$415650A0-21B0-4C65-9B24-902749301C4B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b0c628a46ea54fb9d82b7c2855b2234ed7ab899","datavalue":{"value":{"entity-type":"item","numeric-id":3476279,"id":"Q3476279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b581d39ae2600420cbb9f8f27dbd7a56f3c77ee","datavalue":{"value":{"amount":"+0.925440549850464","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":"Q1801670$EAB17E2C-C454-4ACA-8125-F9785154EAB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e36e981186c9b715b063378fda571325b41032ca","datavalue":{"value":{"entity-type":"item","numeric-id":1108043,"id":"Q1108043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32bf7c983d28a76828d93aa96bab4a7425d1b475","datavalue":{"value":{"amount":"+0.8923552632331848","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":"Q1801670$F874C1A5-DD81-4CF7-824D-BBA264D71940","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"797627ef19b9b043a6c2f16d3b6a5ab3aa5263b8","datavalue":{"value":{"entity-type":"item","numeric-id":3361890,"id":"Q3361890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bb76a8ab82693c1f3e1dc9a8edd6173644fc307","datavalue":{"value":{"amount":"+0.8446375727653503","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":"Q1801670$2FFB9EAC-E361-4E63-8188-EFDD2D56CCFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64e1adbd1396ac37a0e1cdb5bf18a92f944f4f6a","datavalue":{"value":{"entity-type":"item","numeric-id":3736911,"id":"Q3736911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5763b099acf35679e7ae36d5321a3a50fcb2a006","datavalue":{"value":{"amount":"+0.831690788269043","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":"Q1801670$5A1773E6-6825-46ED-B520-15B290FA33B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bea3815c455f21c83d401c11ffc8615ce8fa01bf","datavalue":{"value":{"entity-type":"item","numeric-id":3707421,"id":"Q3707421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d01c5612aeba6407a72d018659de5c44ad033b15","datavalue":{"value":{"amount":"+0.7934846878051758","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":"Q1801670$13C7A679-8143-4FA3-9062-6C3B55430066","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of the embedding problem for hypercube related graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_the_embedding_problem_for_hypercube_related_graphs"}}}}}