{"entities":{"Q1962037":{"pageid":1972779,"ns":120,"title":"Item:Q1962037","lastrevid":47437255,"modified":"2026-01-01T18:17:02Z","type":"item","id":"Q1962037","labels":{"en":{"language":"en","value":"Connected domination and dominating clique in trapezoid graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1395006"}},"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":"Q1962037$13AE18A3-1B6E-49EF-9E68-389914E30DB4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d43f7df5d38b61eab1ed8427e01e0d69a6da56ba","datavalue":{"value":{"text":"Connected domination and dominating clique in trapezoid graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1962037$7517C46B-AA9A-47B4-A6BF-BE216B45B80F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"006b7815aae2b4f893e7f078441fb2889fcfa7e7","datavalue":{"value":"0944.05072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962037$8CA9C328-7CC4-4D3A-8725-EE35F3875A1A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ba1c32c621c061e70ecf4203df0842b9a116bc14","datavalue":{"value":"10.1016/S0166-218X(99)00127-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962037$23DAE81D-A459-4B13-BF56-7CF14C579AC9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"920f73ef2c2ad305bcd7206bbd9ae25684c88cdd","datavalue":{"value":{"entity-type":"item","numeric-id":264184,"id":"Q264184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962037$6D7F8EAC-AF5D-4752-98C1-7FB248D0743D","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":"Q1962037$3D69CE55-9FCA-49A2-9A4C-4DB3172E4FB7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b81887ad3583b3a767523322f66dec54b5a3944a","datavalue":{"value":{"time":"+2000-09-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1962037$DD3180D7-ADEA-493E-ABD6-D088C4A176FC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7c790fab11e3f8d3518340e0a1cfcd6d750a2925","datavalue":{"value":"The class of trapezoid graphs is defined as the intersection graphs of a collection of trapezoids. A set of vertices that dominates the graph and induces a connected graph is a connected dominating set. The smallest set is called the connected domination number for the graph. It is known that this problem is NP-hard. The author develops an \\(O(n)\\) algorithm for finding a minimum connected dominating set in a trapezoid graph. If a trapezoid graph has a dominating clique, the author develops an \\(O(m+n)\\) algorithm for finding such a clique. This algorithm depends on the fact that if such a clique exists, then it has cardinality at most four.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962037$19553A62-67DC-4A47-BB71-3133E048BA11","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962037$7BD3409A-DB58-4CD1-9E7F-39F8129BFBAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962037$4D841164-4DB6-4594-8785-54FB4BB363F9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aceb2834ca6a2d38c013afba37a3bcf8686a8c70","datavalue":{"value":"1395006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962037$5413E39B-2741-4B18-901D-590A66D53C15","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b263e36ca18258b426217c2ef6f3d9276b20c1b3","datavalue":{"value":"trapezoid graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962037$2FB0291A-7D36-482E-9350-181F86388B57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95808b553deada1622b3adfecfe79df17f39c3d0","datavalue":{"value":"connected dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962037$E8338DAA-52D5-4A9A-B144-A449C2366569","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"924979e39df53c43e61bddb3e36d2617afacd37b","datavalue":{"value":"connected domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962037$B489553A-D99C-456B-AD41-C7EAB3E101B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962037$70EB9E29-ACE0-4CDB-A351-4BB75651BA4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcabe08102492dc2cd54fa9819cb8eea09efdacc","datavalue":{"value":"dominating clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962037$C3858886-08BD-45FA-8670-82E589A45EAD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7f532b639e1e3b8bde608d59d2d7e23b01bb3c75","datavalue":{"value":{"entity-type":"item","numeric-id":233441,"id":"Q233441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962037$D82BECB0-1B61-4EE1-A001-B2258BB9F6C9","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":"Q1962037$AE14F735-5A97-447C-9CAF-8F3AFAB84E4B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c25210c6638b02eedcd427748850790c3afba64","datavalue":{"value":{"entity-type":"item","numeric-id":4210127,"id":"Q4210127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962037$C2B0CEFF-7E73-480C-B3F3-20D24567A85A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9eb051f9de617cd276e0ce7b24c6faedc6c1b50","datavalue":{"value":{"entity-type":"item","numeric-id":3797233,"id":"Q3797233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962037$9E4ECEA1-DACA-407E-8932-50297B25F877","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79cc333a398e9d6212f316ca27b812994cbe7ce9","datavalue":{"value":{"entity-type":"item","numeric-id":1111577,"id":"Q1111577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962037$FC60C4D3-3934-4633-B5E4-6E065F08C691","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa577c533ad9f42003c50ffe3eb0b3ccabca305e","datavalue":{"value":{"entity-type":"item","numeric-id":5056173,"id":"Q5056173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962037$39046607-1F2A-4BDF-B1F2-52D71402D6FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ccaadbfdda0c3bd78b54e68c4c36f114e8a7f65","datavalue":{"value":{"entity-type":"item","numeric-id":4290917,"id":"Q4290917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962037$DCD3DF36-D595-4271-85D0-D4ED02EB70A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbed46534388845d219f776d9b682225206fcf03","datavalue":{"value":{"entity-type":"item","numeric-id":3136612,"id":"Q3136612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962037$2A825F72-CCA4-49F8-A303-D20C66D52306","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb16c326ad581e662628d53da6a6b71b6f19bfbe","datavalue":{"value":{"entity-type":"item","numeric-id":1342259,"id":"Q1342259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962037$7090E54E-46BF-4697-A7B7-FA69364584F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d877c10a34370157b70c15856a529e611c667d03","datavalue":{"value":{"entity-type":"item","numeric-id":2583539,"id":"Q2583539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962037$25D98F19-1BE4-44DA-B92A-B77F8B9258E2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03af2f79129f89f2826db90bc614620c8b9ed98f","datavalue":{"value":{"entity-type":"item","numeric-id":881872,"id":"Q881872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a21653b7a11a97abc918a01263aa7abe5b25b78c","datavalue":{"value":{"amount":"+0.8809366822242737","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":"Q1962037$AD821DE1-BEA3-4B90-B35B-3B47D17DE110","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c2ae6f9a613b19f437fc73d625ed4c5918356cb","datavalue":{"value":{"entity-type":"item","numeric-id":2766821,"id":"Q2766821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97ec6ddb5eebc8cd23e8f11e35bf8a8bbcc6812b","datavalue":{"value":{"amount":"+0.880832850933075","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":"Q1962037$CFE27509-8EEC-4E8D-84EA-2B2CC651AE45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b082cf1522850537fb5c659bd8a5bb2c08a27455","datavalue":{"value":{"entity-type":"item","numeric-id":678864,"id":"Q678864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97ec6ddb5eebc8cd23e8f11e35bf8a8bbcc6812b","datavalue":{"value":{"amount":"+0.880832850933075","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":"Q1962037$8A84923C-BF8E-4307-978F-C65D85595D86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8fda2abc18300223e277f06891505f09b052bdc","datavalue":{"value":{"entity-type":"item","numeric-id":3125273,"id":"Q3125273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9154a3db33073f2d140954e12173805af5c948dc","datavalue":{"value":{"amount":"+0.8234724998474121","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":"Q1962037$16BB8197-0870-4DF1-9257-6CE47736CE53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d075957fa53146494e0e24959a81737f7405c8a5","datavalue":{"value":{"entity-type":"item","numeric-id":1356505,"id":"Q1356505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db0b7cb9dca8b3e26c87029f380fe56d56ce1065","datavalue":{"value":{"amount":"+0.8130046725273132","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":"Q1962037$486DB153-D873-45E3-AB63-56B2CFD22FD8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1962037","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1962037"}}}}}