{"entities":{"Q1900141":{"pageid":1910883,"ns":120,"title":"Item:Q1900141","lastrevid":46340475,"modified":"2025-12-24T14:44:07Z","type":"item","id":"Q1900141","labels":{"en":{"language":"en","value":"On some algorithmic investigations of star partitions of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 806411"}},"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":"Q1900141$109B1799-F007-4352-8045-57F6B2232DFE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"36ca75e208710e44c7a6da8503056d99954a5045","datavalue":{"value":{"text":"On some algorithmic investigations of star partitions of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1900141$9948A4E1-2491-4290-9DA1-95C33DFB11B3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"edd3a6d23982048c7ceedb6177b59e750491b46c","datavalue":{"value":"0838.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900141$D975DB1C-64EE-4D9E-8F19-B6A04B239DD2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c26b20fd2c915d94e34f87fb97e150387efa6427","datavalue":{"value":"10.1016/0166-218X(94)00149-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900141$E74C36FA-5783-42EA-8E58-F974D7617A0E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3db7d4aede42575ee9ca1b3081433ec8fcd4840a","datavalue":{"value":{"entity-type":"item","numeric-id":385376,"id":"Q385376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$8BF53F0D-FE16-4D02-B200-80E7B8244045","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ee130c9b7f60a5b1364d597046dcd0740de6d4e3","datavalue":{"value":{"entity-type":"item","numeric-id":1299997,"id":"Q1299997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$AD26046A-5532-4BC1-ADD1-A73CE1B1A5B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9451c4cebeea531e5de3a4edf6d17edf71b2027","datavalue":{"value":{"entity-type":"item","numeric-id":1220947,"id":"Q1220947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$85ED27F3-D6D6-4342-BB27-3A21012AC8FE","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":"Q1900141$4D6A53F0-B2BB-4D1D-9DF4-58D3FC706875","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7d8b01fff4f38bf2448654e1ccdef878bca32dcf","datavalue":{"value":{"time":"+1996-05-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1900141$E0C7376D-295A-471F-9151-C64D994BB461","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"854f41bf58794cb3b854e761fb6894ed917bd6d6","datavalue":{"value":"Let \\(A\\) be a adjacency matrix of a given graph with vertices \\(1,\\dots, n\\). Let \\(\\mu_1,\\dots, \\mu_m\\) be the distinct eigenvalues of \\(A\\), with corresponding eigenspaces \\(E(\\mu_1),\\dots, E(\\mu_m)\\). Let \\(A= \\mu_1 P_1+\\cdots+ \\mu_m P_m\\) be the spectral decomposition of \\(A\\), where each \\(P_i\\) represents the orthogonal projection onto \\(E(\\mu_i)\\). A partition \\(X_1\\dot\\cup\\cdots \\dot\\cup X_m\\) of the vertex set \\(\\{1,\\dots, n\\}\\) is called a star partition, if for each \\(i\\in \\{1,\\dots, m\\}\\), the vectors \\(P_i e_j\\) \\((j\\in X_i)\\) are linearly independent, where \\(\\{e_1,\\dots e_n\\}\\) is the standard basis of \\(\\mathbb{R}^n\\). In this situation, the vectors \\(P_i e_j\\) \\((j\\in X_i)\\) form a basis \\(B_i\\) of \\(E(\\mu_i)\\) and \\(B_1\\cup \\cdots \\cup B_m\\) is a base of \\(\\mathbb{R}^n\\), which is called by the authors a star basis corresponding to \\(A\\) [Linear Algebra Appl. 182, 45-66 (1993; Zbl 0778.05057)]. In the present paper, they give a polynomial algorithm for finding a star partition.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900141$75953DB6-4BC6-4307-B091-91A267348C30","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5a15ba5cd77ddbb51ae11ed560267e558bda35d1","datavalue":{"value":{"entity-type":"item","numeric-id":201638,"id":"Q201638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$6A536C3C-FDB6-4907-9784-A288C353AFE9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900141$7FDD6AD4-B722-416F-8F22-C7D757D757CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900141$84E92622-12EC-492D-BC63-A5097B8DEDAD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b681468093424a78c0f16f5931c131b3209b2df5","datavalue":{"value":"806411","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900141$8FDDE52C-41AF-4AB6-95A1-6566CA68A4F2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"049ed8a155990e3f7831e1a99b3182060bf447f3","datavalue":{"value":"vertex set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900141$367C8F88-FCAC-4102-955A-1B2A8977F4B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc95e5f05c3d9f83a111dedb75f49c2d26fec40f","datavalue":{"value":"adjacency matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900141$0E1E838A-19E4-491F-8111-792D2B93BE1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"811604a75801fcd709c8667f83ea26944825b8d2","datavalue":{"value":"eigenvalues","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900141$75E94A24-4ADD-4D5C-8F33-9C04984FE2EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5f4e235df99f18a2e5ef1ce3b6cb100d7e6bf2d","datavalue":{"value":"eigenspaces","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900141$10E3F288-F848-40F2-8653-7999057BE973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f1962acac5e120904fd7fb9440cccbaca9d251d","datavalue":{"value":"spectral decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900141$8BD68C86-E281-49B1-9FA2-896F4F39019C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e41fb471c5632503b8716f23269ac7a1a49e160e","datavalue":{"value":"partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900141$0B65F2E6-D877-40F5-A94A-24711EE11CF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a14d99a758838751f0c78e1a16c1157064045cf","datavalue":{"value":"star partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900141$7FDC216F-EEC9-46D9-8EAB-FC78DFE5C8A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89c8d085d7ee06114a28ffc6c471093d928f23f9","datavalue":{"value":"star basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900141$A0CCC62D-7A6B-4CC2-9194-C1E4E5FAC949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1900141$FDC89F46-8047-4FFF-B8A4-2762079D1616","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":"Q1900141$9286D70C-737F-4147-8BE8-B3980DFCCCBA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f61c5d68d33f8ea7723f3ac70afbbc88052e3402","datavalue":{"value":{"entity-type":"item","numeric-id":3258697,"id":"Q3258697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$C76C7544-CEC0-4D43-84EE-B746ABEDD24A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3da1be354f5f2961e4c77ff40ee8fbcd3ac01d7c","datavalue":{"value":{"entity-type":"item","numeric-id":1183182,"id":"Q1183182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$D91CDC41-C607-4EEE-8F24-A99BF92C0D3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16e994725b873a6b34aff2979dc436ee1220b2bf","datavalue":{"value":{"entity-type":"item","numeric-id":1210719,"id":"Q1210719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$1B2EDD29-39A4-4837-AAA2-68519CAC2567","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1312a34b6a8327be1e35714f2f181547c026a788","datavalue":{"value":{"entity-type":"item","numeric-id":3907599,"id":"Q3907599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$2FE8632B-CD7D-499B-9DBA-9A15C6248701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c996dbe210b2055ebf639b96d6e8812cac3200d6","datavalue":{"value":{"entity-type":"item","numeric-id":2365658,"id":"Q2365658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$EC6AA3D4-417C-408D-81FD-8040E77DF13C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2f1418cda1b0b9a975cd52bf50e78acbd1bc719","datavalue":{"value":{"entity-type":"item","numeric-id":3205244,"id":"Q3205244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$0C32D25E-FBD4-4B17-8E4F-61BF1FEDCF9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$87098A54-DA34-46D9-986A-A3712D4AA93C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$649A8155-1084-4AA9-9E13-0390EBD3C4C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"403ed34f588585da892f33961aef00710019fc5e","datavalue":{"value":{"entity-type":"item","numeric-id":4281313,"id":"Q4281313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$659C8DA6-3243-4A64-BA24-E94CE74D2E2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7c50a159b535097321ba7243331321c2fcb95ad","datavalue":{"value":{"entity-type":"item","numeric-id":4172091,"id":"Q4172091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1900141$41F17DD0-F60C-44EE-B023-09CC50D4C01C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"de9e13862862e2c7265800d81271696eeaa280df","datavalue":{"value":"https://doi.org/10.1016/0166-218x(94)00149-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1900141$CBF362B2-7EE4-4BE4-B92C-EAC302321DB7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a14b2ea856cceb4ec654ac5708ed1d84f6c22c72","datavalue":{"value":"W2063596425","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1900141$5A02902F-2DD1-41DC-BFA9-FDCD84DC99AC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40b65cba9cdcf5f76a74e0e9b62c3f3bb2f3e6a4","datavalue":{"value":{"entity-type":"item","numeric-id":1899409,"id":"Q1899409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e13215dec550568bd6df8096a955cd9f2e891fdd","datavalue":{"value":{"amount":"+0.8578720688819885","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":"Q1900141$69DB578C-8CA3-4369-8EA0-8779DD1F196B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb546a5ddcc257c649c145faae70261b813c6887","datavalue":{"value":{"entity-type":"item","numeric-id":4853929,"id":"Q4853929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1088a2af4a1a8d3eab8cd495ae378bba9cd66afe","datavalue":{"value":{"amount":"+0.8023295998573303","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":"Q1900141$8E87EEF5-76F8-43A8-922D-24CFEF044234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0247fc9cc6fae63cd92493e750926b7ebbce110c","datavalue":{"value":{"entity-type":"item","numeric-id":2785496,"id":"Q2785496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c02a9fe58ad81dd3c7eaf3f4c361b17f4fe46908","datavalue":{"value":{"amount":"+0.7950846552848816","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":"Q1900141$BD29E518-5A9A-4FF4-979F-66646D03D440","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1900141","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1900141"}}}}}