{"entities":{"Q674438":{"pageid":676287,"ns":120,"title":"Item:Q674438","lastrevid":63625566,"modified":"2026-04-11T14:26:40Z","type":"item","id":"Q674438","labels":{"en":{"language":"en","value":"An algorithm for finding homogeneous pairs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 986695"}},"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":"Q674438$882B813D-1CE8-43B5-A425-DD899F9AAAC9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9f748a993402a59f9f08f52731f0fa269954221e","datavalue":{"value":{"text":"An algorithm for finding homogeneous pairs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q674438$CD1B6ED5-C048-4000-AE2C-D6970BAF7170","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4cd9cc08bccf1ec07c5bd2fa4858c779de2c0dbb","datavalue":{"value":"0874.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674438$230106AF-A648-4C7F-9BD7-812E50B2E832","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"51877ac7bd5d3614c47983874e6414d7a8584188","datavalue":{"value":"10.1016/0166-218X(95)00090-E","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674438$6FAB75B9-A4D4-4BA8-A550-54A2C3B293C5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0dd41e0c9fd856e61a9a7227322992849270ab58","datavalue":{"value":{"entity-type":"item","numeric-id":293305,"id":"Q293305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$41AC04C9-72FB-4688-8D27-7E351ECCB9F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"33602871ceeec996c1031332ead2242c6f784054","datavalue":{"value":{"entity-type":"item","numeric-id":293306,"id":"Q293306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$A69719A0-1BC2-4261-AA6D-D6BD0EC0DF3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d98a938c7c496671aebe9d069bbd3d70f74a635a","datavalue":{"value":{"entity-type":"item","numeric-id":661944,"id":"Q661944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$E8A40011-4085-4E60-92C4-80E5731CBC63","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":"Q674438$6470F935-E98B-4ED5-A4D1-93870487B3E8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1c9ff9641120a3295589b2943ae9aeb635bcb9a6","datavalue":{"value":{"time":"+1997-11-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q674438$6E4DF221-8201-4F2C-BC70-20A47C062EC0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q674438$4C3C0D63-B6F7-4BBB-AC0A-86A9B8E33CFD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dab26b49bfd5f1179e28696767cddb34f6320068","datavalue":{"value":"\\((Q_1,Q_2)\\) is a homogeneous pair in an undirected finite graph \\(G= (V,E)\\) if \\(Q_i\\subset V\\) for \\(i\\in \\{1,2\\}\\), \\(|Q_1 |\\geq 2\\) or \\(|Q_2 |\\geq 2\\), \\(|V \\backslash (Q_1\\cup Q_2) |\\geq 2\\) and every vertex \\(v\\in V\\backslash (Q_1\\cup Q_2)\\) is adjacent to either all or none of the vertices of \\(Q_i\\), \\(i\\in \\{1,2\\}\\). Homogeneous pairs are of interest in connection with the strong perfect graph conjecture---it is known that minimally imperfect graphs contain no homogeneous pair. This paper describes an \\(O(mn^3)\\) time bounded algorithm for determining whether a given graph contains a homogeneous pair, and, if possible, for finding one. Hereby \\(n=|V|\\) and \\(m=|E|\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q674438$E38144DD-828A-4036-8B8D-886D8F7D616E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5af1aa80224172db75f7ae535f0d2940793ea880","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$37D9FC90-40CF-41B8-A7FA-03A78D9489BB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674438$AB56E9ED-9044-4862-BFB5-AF3C1A0471AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674438$4E56C825-07AD-464F-82F0-81AE259A6EEB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"89de5decceaf02fdad32bbec5540c1cfd3c1444e","datavalue":{"value":"986695","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674438$BE0112D4-E0C0-4103-B159-7C7593D3C6F8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q674438$36F5A37F-25BA-45CA-9E81-761CF6610DCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a431ee097b748dfe9350f936a7a4b7499880a5d","datavalue":{"value":"homogeneous pair","type":"string"},"datatype":"string"},"type":"statement","id":"Q674438$35B9831F-E104-4434-B11D-5666AE04BA51","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":"Q674438$77630CD5-0BD2-45D9-8E63-4B02DF427A64","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf035d2fecb7e445991dd16e141f37bab3768a8","datavalue":{"value":{"entity-type":"item","numeric-id":1254112,"id":"Q1254112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$2F6A99D2-613E-431D-8AF3-5A887010B5AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54f80bd66875089f385bc846e7e7f8ca82fdf2a5","datavalue":{"value":{"entity-type":"item","numeric-id":1095938,"id":"Q1095938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$F09D7F08-01A8-4604-871D-0CC8EDFB622D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01daeab766d175bddc9f50c88df891bc3bb25b36","datavalue":{"value":{"entity-type":"item","numeric-id":3676177,"id":"Q3676177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$ACEDF84C-411E-42F4-80F5-DF4D4E284F43","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":"Q674438$05601C41-8A0F-4FDC-A759-C22FC9661236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$2E23F4E6-E166-4D18-87D9-B81B0378F82D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c998f37ea2af5fb09fab159d72a9dd7f47c2d7d1","datavalue":{"value":{"entity-type":"item","numeric-id":1235707,"id":"Q1235707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$A554AC10-2AB3-49DB-95E5-9FB85EE07E93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70932f1cf740819121b6dff2db80775f668b9c68","datavalue":{"value":{"entity-type":"item","numeric-id":3216686,"id":"Q3216686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$C9A57D56-3B64-4F37-A612-E82E9F5BCE6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddbe097f62791bcc42fe71dd30e6b393e0a8c6f9","datavalue":{"value":{"entity-type":"item","numeric-id":2553445,"id":"Q2553445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$79AD088A-86A4-4DB4-B4A0-345BE65AB5D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4ea2af1a8c93ceb977d8f389518ef463650adb3","datavalue":{"value":{"entity-type":"item","numeric-id":3823808,"id":"Q3823808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$432A11EE-0A7E-473F-9C88-4E052B01DD85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a30671902fb372ed73af487ee47e19cbef1c982e","datavalue":{"value":{"entity-type":"item","numeric-id":1201812,"id":"Q1201812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$101692BF-1349-4538-B729-7D9F27FE52BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674438$EC4E2207-E2DE-4AFD-97E9-2BA4240552A3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"34dfad5bfe2d8ab7b8a40d14179a8800c685eb25","datavalue":{"value":"W1979621874","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674438$C7DE6D61-D14E-4E21-927F-CA46BA15711B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d331f23293554e3138f5276f92970d5431796ace","datavalue":{"value":{"entity-type":"item","numeric-id":2894487,"id":"Q2894487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aeb02f1bec80883c64621a55d5b665f68524ae9c","datavalue":{"value":{"amount":"+0.8188960552215576","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":"Q674438$90786283-00BE-4EAD-9DDB-ACF37C142D0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"390f0924a3c35e0a1213e59adbe10852a281af3a","datavalue":{"value":{"entity-type":"item","numeric-id":850795,"id":"Q850795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2aed94903f3c1131b0782752f2686972d1491c87","datavalue":{"value":{"amount":"+0.7886696457862854","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":"Q674438$31693793-3AFF-4D3A-B9C5-0BF6D7BE9EB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"500ecf952e4c40b373c9881a3db44494ab5a8516","datavalue":{"value":{"entity-type":"item","numeric-id":1607076,"id":"Q1607076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f6442b4efdea472bf0e6866e92030cf4e2f3795","datavalue":{"value":{"amount":"+0.7814267873764038","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":"Q674438$E4DCC583-3A17-4B5F-A240-79F1E27EE2AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9c37abd758bf28b70cf3bfcdbf96f1f9b23be63","datavalue":{"value":{"entity-type":"item","numeric-id":844163,"id":"Q844163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0d2b0e194a9191716bbee13908cd22ca8b47815","datavalue":{"value":{"amount":"+0.7776640057563782","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":"Q674438$72CB8396-4772-49A4-BDE0-84FAF64C2690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d0d386feab66a4808db004d935a5f5111d4db6f","datavalue":{"value":{"entity-type":"item","numeric-id":1814097,"id":"Q1814097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcb63c772d9cca6fb06e215e6473a3180178dc6d","datavalue":{"value":{"amount":"+0.7733951807022095","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":"Q674438$5D8F929A-9467-472E-A611-92E2E8FB1DDA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An algorithm for finding homogeneous pairs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_algorithm_for_finding_homogeneous_pairs"}}}}}