{"entities":{"Q788002":{"pageid":789850,"ns":120,"title":"Item:Q788002","lastrevid":48670354,"modified":"2026-01-05T13:49:26Z","type":"item","id":"Q788002","labels":{"en":{"language":"en","value":"Domination, independent domination, and duality in strongly chordal graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3841908"}},"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":"Q788002$E7951037-3924-44FA-84B6-FC1B32855A74","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ab0c14dd19292ef9830660ef3b3fff3b5a5976fa","datavalue":{"value":{"text":"Domination, independent domination, and duality in strongly chordal graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q788002$0F8E86DF-E6C0-4B80-9661-9F8D8E244A0E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8158b89e7e92fad9cb6c920378cd023361c76b42","datavalue":{"value":"0531.05045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788002$DB198D2F-5B7E-4DC0-BFD8-7FCE7F679A89","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dd1ec666b213c6706ff5492614f4e78c8791ff0f","datavalue":{"value":"10.1016/0166-218X(84)90061-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788002$717656B2-03D7-427C-9E07-AC260421B716","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4279505aca0e053329b78fa731a2e6a34ac80564","datavalue":{"value":{"entity-type":"item","numeric-id":686242,"id":"Q686242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$552C9AB0-38AC-4085-9852-7FE78E2B0DF4","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":"Q788002$35A5E811-19B2-4D68-BC6C-4B8C5173A754","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q788002$23A43031-9942-4CF9-880B-49D85204FF88","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f35eb80c8d61ecf287505dc96e5a8bfc4bbe30f8","datavalue":{"value":"Polynomial-time algorithms for finding minimum weight dominating sets and independent dominating sets in strongly chordal graphs are presented in this paper. The algorithms are based on linear programming formulations of the problems and consist of two stages: in the first - a greedy algorithm is used to solve the corresponding dual program, and in the second - feasible solution to the primal is read off. In the second part, a relationship between strongly chordal graphs and totally balanced matrices is utilized to show that the domatic number achieves its theoretical lower bound in strongly chordal graphs and to efficiently solve certain optimization problems for totally balanced matrices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q788002$7AE9E1EC-4D52-4FB3-8B4B-AB208D64ED4F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788002$8DECCE6B-76D1-4242-939D-D292A58FE6B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788002$C134C4A7-ECE3-4E8E-9B40-6EE0F3544EF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788002$001C534C-8A85-4031-A558-57FC0BB6C303","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3d0f093d9589a1e56abc86c830542240d3c542f9","datavalue":{"value":"3841908","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788002$B6E2BE41-FC3C-4BC1-9943-5F57CECA6785","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98cd989d2b882bc1595c93c498030207172a21eb","datavalue":{"value":"minimum weight dominating sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q788002$656B6310-6F35-4083-B087-F843605AAA83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a7cc8628f5036ee2a953075b5877bf4afef8e7a","datavalue":{"value":"independent dominating sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q788002$97E635FE-1E94-4F96-BB22-EE10A35CEBF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79cf282eaa552eec4f111c6d9931badbca1b9b94","datavalue":{"value":"strongly chordal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q788002$68D95C5E-FF2A-4E13-9BE4-106BADCDCDC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1f7e3e9784d3bd2e9945bb4540d3e0786b105df","datavalue":{"value":"totally balanced matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q788002$B12A148C-4D86-4BC0-9188-5772F426DCA9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9d2038bc5b75235dbb16f529946235e1ed908b44","datavalue":{"value":{"entity-type":"item","numeric-id":583878,"id":"Q583878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$F760A705-BB4A-491B-9246-D7F8B5701298","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":"Q788002$62F01C09-93C2-44E5-B98D-B6FCEB1AADAD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b717ce5476163967b0df9674233704df8f3864c4","datavalue":{"value":{"entity-type":"item","numeric-id":3344216,"id":"Q3344216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$D2928263-FD83-4297-BAB1-138EA533E380","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15abf164381e188ffaaaa88e1e51e9c0b99bc916","datavalue":{"value":{"entity-type":"item","numeric-id":5659570,"id":"Q5659570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$0F7E311D-4692-47BE-BD46-E860DDE24103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05a67387b4f64ed453ef1ee837d4133852bc63cd","datavalue":{"value":{"entity-type":"item","numeric-id":3206969,"id":"Q3206969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$912C7863-6ED2-412C-9023-9709224E0CF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d207798ab208e2d6135aa6be4f21281e7287368f","datavalue":{"value":{"entity-type":"item","numeric-id":3944643,"id":"Q3944643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$E0FB6A09-A76C-4C60-8A52-1596966A9F8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6b351fad9657df3efe83a4f8f8f50558953cda3","datavalue":{"value":{"entity-type":"item","numeric-id":3697054,"id":"Q3697054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$B4130447-B9C6-456A-821B-463DD0060D74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ae7ddb3329597da82f842e9614bf124730cbda4","datavalue":{"value":{"entity-type":"item","numeric-id":1219556,"id":"Q1219556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$4B5058A0-4DD9-4490-BB37-55C35B93E83C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b56aa07beffcf5cd4668ceb40b044197d8e5f8b9","datavalue":{"value":{"entity-type":"item","numeric-id":4163261,"id":"Q4163261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$65824E50-3A01-4EA7-A39E-2F14FA35073C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e5b93f48232aab346591ab4038496b4873154f9","datavalue":{"value":{"entity-type":"item","numeric-id":3963030,"id":"Q3963030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$7DDEAA53-0E9F-44AB-A9D9-A18130907CBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9aff4421d83319ba553decf5ffccebfa072fb3c1","datavalue":{"value":{"entity-type":"item","numeric-id":1169487,"id":"Q1169487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$328F60FF-53C1-4552-8CBC-A0A03AC11F53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6ba8beca23cdaad0ac4c8fdb9394466e17ade7f","datavalue":{"value":{"entity-type":"item","numeric-id":1051004,"id":"Q1051004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$4F253615-77A7-4B9D-8504-5E32499A4E58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78cd4360ea9f152efe54d233fc8cd48df1287364","datavalue":{"value":{"entity-type":"item","numeric-id":4133404,"id":"Q4133404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$40E932E9-278A-4DB6-AFF4-D62789A689DD","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":"Q788002$6970424E-067C-48DF-8403-F0DD33A77560","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b87f240b74f3f9df9c2b55fdb1be42ca8217e47","datavalue":{"value":{"entity-type":"item","numeric-id":3691772,"id":"Q3691772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$8355BB29-D392-455F-9BAA-AA7935B30CCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97236fbeb6b6b2bba840114a8ba2f0448b9619f9","datavalue":{"value":{"entity-type":"item","numeric-id":4197641,"id":"Q4197641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$136829B5-D8C9-4107-B925-439B8F3CD802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ec4868dba1b37d1adb8bb9f6a23d6c0a862f5","datavalue":{"value":{"entity-type":"item","numeric-id":3880849,"id":"Q3880849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$8F5F3AE0-A068-4809-A53D-6CB142D63DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45e3d015a04e002c669009011d532301aac066cf","datavalue":{"value":{"entity-type":"item","numeric-id":1251239,"id":"Q1251239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$0D7DF1D4-7329-4240-9B30-E4CC4687CAF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a3f4f623c55f4103180bc7ed3e80e030c1afd8b","datavalue":{"value":{"entity-type":"item","numeric-id":2545884,"id":"Q2545884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$22077600-274C-4209-B097-D3E7D79F5460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8592b19f12bd09556a4de81ad49778d747c4f77b","datavalue":{"value":{"entity-type":"item","numeric-id":4124209,"id":"Q4124209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$AEDA75C4-0A94-4D12-A4DE-4414BABA9E5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00b438f56102450eb07da7aa4f6d27bc8f011f91","datavalue":{"value":{"entity-type":"item","numeric-id":5643783,"id":"Q5643783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$F30FD9C4-FF0B-4182-A729-78E7B578DBFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6a7a007a1f46160063a923727ad34889e92b344","datavalue":{"value":{"entity-type":"item","numeric-id":4119239,"id":"Q4119239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q788002$95882088-6347-4540-8514-05C2E63C893D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"08848ca06659324b29a0bf19e313a5f481376387","datavalue":{"value":"Q127740357","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788002$CA5070EE-008D-4FE8-A7CA-89895C80A981","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"80aa33eb169ab4f414bd3799513cb60d7891e179","datavalue":{"value":"https://doi.org/10.1016/0166-218x(84)90061-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q788002$13DB40DF-AEBA-495D-BAAF-4637A91EB639","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"65164376b0ed470bf0e51704e4aee909049914c7","datavalue":{"value":"W2050228489","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q788002$81593548-943C-459F-9167-68C34E6F3962","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ec6f28da156775aa34fe60f8e85efecc0464cc9","datavalue":{"value":{"entity-type":"item","numeric-id":805638,"id":"Q805638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6bc2c997a5cf357cfb226dce089d8993ef628b6","datavalue":{"value":{"amount":"+0.8321290016174316","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":"Q788002$1362CB87-AF63-46FE-A911-585483323D95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbd8cfc595b9677f2ef2b4e673a63bc2badfa74f","datavalue":{"value":{"entity-type":"item","numeric-id":3782805,"id":"Q3782805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d7d8e6cf60259744ad6510c14c516d22b972fbe","datavalue":{"value":{"amount":"+0.8274165987968445","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":"Q788002$22A22E97-F22D-4619-A247-AFE5AD88A8F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3048cfe880df0542af22ac58f4f513f6b2cd7f37","datavalue":{"value":{"entity-type":"item","numeric-id":477653,"id":"Q477653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d130042fa69724b401be2560616c968b5f192069","datavalue":{"value":{"amount":"+0.8222511410713196","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":"Q788002$FED32C13-E192-4F3A-B840-07D1DA496337","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1e2fb95d60157c6ef5fe077649a5dc454f6192e","datavalue":{"value":{"entity-type":"item","numeric-id":3701460,"id":"Q3701460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ad208b53460ce24a1b4ea1c908c424403adb85a","datavalue":{"value":{"amount":"+0.8218213319778442","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":"Q788002$119A1DB0-8005-4F61-AEC1-02F08DA2005E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bfc61b2ade57dcbeeb03c182217d897aa5184b0","datavalue":{"value":{"entity-type":"item","numeric-id":1195488,"id":"Q1195488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"842aa1190fcd3d9c5e94afb100a41d05be571476","datavalue":{"value":{"amount":"+0.8215170502662659","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":"Q788002$0BB13E23-06FA-45CB-AC98-0D94FACA5388","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:788002","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:788002"}}}}}