{"entities":{"Q1917348":{"pageid":1928090,"ns":120,"title":"Item:Q1917348","lastrevid":46455456,"modified":"2025-12-24T19:55:48Z","type":"item","id":"Q1917348","labels":{"en":{"language":"en","value":"Algebraic approach to fasciagraphs and rotagraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 897435"}},"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":"Q1917348$1CB2142F-D770-4BF9-8197-EEA836718425","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7cc524c27f5eb598afffd7a226c4f73d1452b408","datavalue":{"value":{"text":"Algebraic approach to fasciagraphs and rotagraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1917348$F7A3ECCB-44FB-49F1-A003-C8756885F0D2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7e85b7ce97195454122b198378766e36013f38fb","datavalue":{"value":"0848.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917348$A3141297-EF93-4480-A29B-7ABB5BA28565","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6587c2baa795d05066a0128bf397c57e874cbeeb","datavalue":{"value":"10.1016/0166-218X(95)00058-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917348$1C06896B-52A6-407E-B78C-2FDF8A1A9F2D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ceb1fcf1c75dc367d934ec93f0fd1abaa5c7756","datavalue":{"value":{"entity-type":"item","numeric-id":251101,"id":"Q251101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$C609F212-A528-4F30-869B-F0207D3046A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"88a2fd89e080aa8c20a8fec4304c5082882836fd","datavalue":{"value":{"entity-type":"item","numeric-id":186164,"id":"Q186164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$56993D58-E80D-4DDE-8DF0-C6F0EBD627A0","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":"Q1917348$D53F031C-FDA0-4801-9D0E-AF5DC327CCDE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0271cbeeb928d08d15c68ab78652d82beab9308f","datavalue":{"value":{"time":"+1996-10-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1917348$87E12D1D-F85B-47A5-8F3C-068653BA2477","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d1da02449432b12a02b0293f3db30c797fe3d83c","datavalue":{"value":"Let \\(G_1, G_2, \\dots, G_n\\) be a set of arbitrary, mutually disjoint graphs, and let \\(X_1, X_2, \\dots, X_n\\) be a sequence of sets of edges such that an edges of \\(X_i\\) joins a vertex of \\(V(G_i)\\) with a vertex of \\(V(G_{i + 1 (\\text{mod } n)})\\). A polygraph \\(\\Omega_n = \\Omega (G_1, G_2, \\dots, G_n, X_1, X_2, \\dots, X_n)\\) is a graph with  \\[ V (\\Omega_n) = V (G_1) \\cup V(G_2) \\cup \\cdots \\cup V(G_n) \\]  and  \\[ E(\\Omega) = E(G_1) \\cup X_1 \\cup E(G_2) \\cup X_2 \\cup \\cdots \\cup E(G_n) \\cup X_n. \\]  If every \\(G_i\\) is isomorphic to a fixed graph \\(G\\) and every \\(X_i\\) is equal to a fixed edge set \\(X\\), \\((1 \\leq i \\leq n)\\), then the polygraph is called a rotagraph denoted by \\(\\omega_n (G;X)\\). A fasciagraph \\(\\psi_n (G;X)\\) is a rotagraph \\(\\omega_n (G;X)\\) without edges between the first and the last copy of a monograph \\(G\\). In this paper, the authors use an algebraic approach to solve problems on fasciagraphs and rotagraphs. Among others, they show that the domination number of fasciagraphs \\(\\psi_n (G;X)\\) and rotagraphs \\(\\omega_n (G,X)\\) can be computed in \\(O (\\log n)\\) time. This is an improvement over the previously known algorithms for computing the domination number of the grid graph \\(P_k \\square P_n = \\psi_n (P_k; X)\\) which were in \\(O(n)\\) time (for a fixed \\(k)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917348$AF7A0A1C-44F0-46A4-9032-D8844529DD9E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917348$4DFE8FD9-F8CE-4A9F-AF63-1B55A02C9F21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917348$78BBB983-9B0D-4CFB-AAD2-9026438B14D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"73f56080a02a8fe5d6ce3d78aad9fc6e7b863188","datavalue":{"value":"897435","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917348$B167CEE4-1FAE-44A2-A161-8086AFA8ABD1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58c34cfe223316591f56cdf41b66e4b6aa918f66","datavalue":{"value":"polygraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917348$D8E392A9-7E1B-4232-BEC9-D34CE36244F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"780e53c61cbecab7fe2f0b47c09718f992453ea8","datavalue":{"value":"rotagraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917348$3807E782-3EFF-4D67-8213-30EF5E4AB805","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c2f1187e6b36ac9f61bb736113a3cfeeec3cb32","datavalue":{"value":"fasciagraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917348$6B917A18-9182-48A7-9368-E089D0E2E916","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3267d14ab3c644208190b057ee58cacbeb7fa5c7","datavalue":{"value":"domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1917348$15BEF1D9-FDB7-4E16-A9CC-42BC888AEFFA","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":"Q1917348$F939E0C4-6E14-4FDB-B26E-CBF8F3989EAB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"924e802243b4f51c1822e67211b88d08172a8079","datavalue":{"value":{"entity-type":"item","numeric-id":1062758,"id":"Q1062758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$5C90C758-548F-430E-9749-B101722E552C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf73aba229b23f389841856465d1ea7418d3ff2b","datavalue":{"value":{"entity-type":"item","numeric-id":3042417,"id":"Q3042417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$633A7D98-4ED2-4F27-AB8A-6AAD2B28A5DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fd859f69142e25bf1b2e6bc770aa8a56fd2cde6","datavalue":{"value":{"entity-type":"item","numeric-id":1103634,"id":"Q1103634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$51448DFF-F761-46E9-96EA-BCD31EFF995F","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":"Q1917348$C77AB748-54F2-483D-B37D-AB77031C6E58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36985d0b4f35f6d011b276000c29b380d5024d22","datavalue":{"value":{"entity-type":"item","numeric-id":4693347,"id":"Q4693347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$6C6441F4-B05C-4A4D-8BB9-B6B80883C6B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f380170dd9de5e69fb40eb46470ac085e19dc87a","datavalue":{"value":{"entity-type":"item","numeric-id":1174134,"id":"Q1174134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$BF7A5AD4-274C-4E5E-BA15-90E5B05E0CE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07618f11017b21ce5bd2e212b50fb69d7747bc33","datavalue":{"value":{"entity-type":"item","numeric-id":3758883,"id":"Q3758883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$32BB956D-6902-4F80-85DD-510C1641CB14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84badcaedd2a851acc03befab949d0eb535d2494","datavalue":{"value":{"entity-type":"item","numeric-id":3777474,"id":"Q3777474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$268E8484-4C5F-4981-A3B5-427A8E1B2F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b49197929288f9de080d26326dbced0d14b3ab6c","datavalue":{"value":{"entity-type":"item","numeric-id":804605,"id":"Q804605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$4E015C43-C195-4C5C-9635-62C854933D9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41f1dff4a7be7c958924f903efb5600d1105fb27","datavalue":{"value":{"entity-type":"item","numeric-id":3680873,"id":"Q3680873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$82CC7F51-39D1-465F-B0C8-C3B0E9040A1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0faf3e4770a3272511958ac1646e7c62c1dc127f","datavalue":{"value":{"entity-type":"item","numeric-id":3708842,"id":"Q3708842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$17BD5DE0-D87A-4B97-9EF3-902299E32B6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fae5ed26ff3890662f3c598c46ac06fbee65626a","datavalue":{"value":{"entity-type":"item","numeric-id":1891923,"id":"Q1891923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$5D44F95F-D912-47D0-BFB9-A17340F198E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6760c1a0ed84f473ebf9c19dbb4d05bbf42b9a5e","datavalue":{"value":{"entity-type":"item","numeric-id":3751592,"id":"Q3751592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$0E59998A-E8EF-471E-8EB9-BD91D4236272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36f5833550e269623349e512f5f9ffd53bbcd5fc","datavalue":{"value":{"entity-type":"item","numeric-id":4385515,"id":"Q4385515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$43BEC10A-B1FD-4F62-A835-83ED2C56AB97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12cfce52587a468e21e74af668ec3c80e8bb1ef4","datavalue":{"value":{"entity-type":"item","numeric-id":1254258,"id":"Q1254258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$20CCAB63-6DD5-4CAF-A4BC-5F14B346D1E6","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":"Q1917348$43A78724-E8A9-425B-B365-47629B806CD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6688f872d12b516f52bd5e7e1bef951250e9d37","datavalue":{"value":{"entity-type":"item","numeric-id":4326192,"id":"Q4326192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1917348$16855917-24BC-42C8-BF96-6A5465848C56","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b4b05a9cca032d3d7e111bbaf216a17aff6761c1","datavalue":{"value":"https://doi.org/10.1016/0166-218x(95)00058-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q1917348$00BFAB54-9E26-427B-B286-042BC80A9567","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7c341f30d2e71c110eaa2f99ff85293bad760212","datavalue":{"value":"W2000865051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1917348$E6E42488-D0ED-48E2-A107-886FEF2A4912","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7dbbc78115b059506f54c6dbaa2c064afbc5de3c","datavalue":{"value":{"entity-type":"item","numeric-id":4934361,"id":"Q4934361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3797a7c60cff52ee6025a3db35b111b18ef9064","datavalue":{"value":{"amount":"+0.8754825592041016","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":"Q1917348$9F237687-62BE-456D-B8C0-D2A559D50C20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70d926e9832bf0ba3915574d5cd32992838bb48d","datavalue":{"value":{"entity-type":"item","numeric-id":442402,"id":"Q442402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"344963937ebf869751fbc92a8c831ce84fecc192","datavalue":{"value":{"amount":"+0.8292551040649414","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":"Q1917348$05304432-CE3A-432F-AB62-23AB0B19DE05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c4756566da4a35a7c4a0667b912dcb5be072184","datavalue":{"value":{"entity-type":"item","numeric-id":284833,"id":"Q284833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c34c82458122c9a60273d9b8c688dfae20e3d49","datavalue":{"value":{"amount":"+0.8191289901733398","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":"Q1917348$28F3F731-3C3E-42D2-9AC4-E48892C0EC28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4166630aa902f955703e14e433f426f70a3457a","datavalue":{"value":{"entity-type":"item","numeric-id":1377616,"id":"Q1377616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c679a5aa40c12007251cbbbc7d498a53004b713b","datavalue":{"value":{"amount":"+0.8093921542167664","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":"Q1917348$2CC47AE6-A90C-4BA2-91B6-2403BA2361BD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1917348","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1917348"}}}}}