{"entities":{"Q1962038":{"pageid":1972780,"ns":120,"title":"Item:Q1962038","lastrevid":47437261,"modified":"2026-01-01T18:17:02Z","type":"item","id":"Q1962038","labels":{"en":{"language":"en","value":"Domination and total domination on asteroidal triple-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1395007"}},"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":"Q1962038$CF646163-6485-45C5-B0F1-2CC536311A34","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a1a1d0fe27b78013188b617d40c8aaae7a0bd618","datavalue":{"value":{"text":"Domination and total domination on asteroidal triple-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1962038$72C56BAF-23EF-4160-8CAB-378963B84965","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b25bec33b7a2bbf3e4d951f369047236cec6922b","datavalue":{"value":"0943.05063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962038$46C26100-124F-4723-90B1-EB215DC63E2C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"43706bdb6efae009ce959b5360ba70337c4db8c4","datavalue":{"value":"10.1016/S0166-218X(99)00128-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962038$B7E9AD43-BADF-4A87-AB9E-5EF57EF6F5F2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5adf86a269713b0e23511a52caceaa2ff6312793","datavalue":{"value":{"entity-type":"item","numeric-id":190506,"id":"Q190506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$6F260732-6181-444E-BF09-5FBA7818E40B","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":"Q1962038$50722C5D-8537-486A-8C40-A309CB76BCF1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6586588445949d2fbb40c4309ca2cd89ad6a7878","datavalue":{"value":{"time":"+2000-08-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":"Q1962038$FED7CDB5-9130-4050-880F-86247B5B5E26","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"351136177db13c363da76f9bada92195e89af1e1","datavalue":{"value":"An asteroidal triple (AT) of an undirected graph \\(G\\) is a set of three vertices of \\(G\\) such that there is a path between any two of them avoiding the neighborhood of the third one. A graph is AT-free if it contains no AT. The structure and algorithmic properties of AT-free graphs have been studied extensively---AT-free graphs generalize well-known graph classes such as interval, permutation, trapezoid and cocomparability graphs.   This paper presents polynomial time algorithms for solving the problems DOMINATING SET and TOTAL DOMINATING SET restricted to AT-free graphs. These algorithms even work in polynomial time on graphs with dominating shortest path---a generalization of AT-free graphs. The key idea of the algorithms is to compute a certain type of dominating set by dynamic programming through the levels of a BFS-tree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962038$CF3498F0-98B2-4722-BD50-7F621D28AAB0","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":"Q1962038$E09AA86F-973F-4DDE-99BF-D3DB5A225939","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962038$C0173ABF-3C99-4B93-BC34-EF05CD355B65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962038$7B730B60-1A7B-4B05-B9A9-D3458801BE66","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7c51aa85bfc6e1614d21e6b3f4c1eafe8218c9db","datavalue":{"value":"1395007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962038$03FFF0D9-9EEA-4D4C-8C32-6FC1F95672B6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c043eb6b18f919f6025564ffa2fe61a03f5732dc","datavalue":{"value":"total domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962038$3212E8B0-A88E-4CCC-88EF-2983B507E1B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee9339b1141db17d90b6638fb1e6651e36e25105","datavalue":{"value":"asteroidal triple","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962038$CC9A0A99-8F2D-41A6-A5F4-9A6EDAF7F3F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa7ab4fd389eb124a320e77dbb93bd6b5d183aa7","datavalue":{"value":"AT-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962038$8EABFA56-899C-4FB4-8D56-A4C9ABF4F4EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d85c121e6e6200a1d4667137fca957de2656737","datavalue":{"value":"polynomial time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962038$ED3A3208-F0DF-4DEC-B967-A9A11131040A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962038$2D15A7F8-65D9-4FE3-A20E-037DE829E04B","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":"Q1962038$32D51882-52FF-4470-80B2-8130AFD564C2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"770bb68de47752f527df3eb5fd0239815f0bd638","datavalue":{"value":{"entity-type":"item","numeric-id":3751595,"id":"Q3751595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$40640702-CB11-43EC-A76C-4509F3F3E1A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31650e5a012e79c170a9c94fd699edaa2149c588","datavalue":{"value":{"entity-type":"item","numeric-id":5060107,"id":"Q5060107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$5353A70C-63EF-4D76-8D9F-BFC9FA8CE841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f81e420061814907361d2262102b5f1493baceaa","datavalue":{"value":{"entity-type":"item","numeric-id":4572004,"id":"Q4572004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$97849FBF-B769-4868-B4F2-DE5A6EB7FE90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44fc750bc29c7ea3b2be952d54a16267cee2cbbf","datavalue":{"value":{"entity-type":"item","numeric-id":1117254,"id":"Q1117254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$B87BC942-86D4-437C-A06D-85C8C99E2FB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11b0885344a22f85055e56d17bd5625326fbf14d","datavalue":{"value":{"entity-type":"item","numeric-id":673002,"id":"Q673002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$C479C3D8-0FED-4759-855B-D661567B64FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aab885e59c8d93d41d21fa0e7e02bfe283e442f","datavalue":{"value":{"entity-type":"item","numeric-id":4645186,"id":"Q4645186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$8FB61B76-CA7E-43B8-BCAA-876497FACF14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccd77119adc0a982791c6b5078f2abd858101adc","datavalue":{"value":{"entity-type":"item","numeric-id":4377431,"id":"Q4377431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$76FF2DC6-3530-42CE-AD8F-17EF2CEEA087","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fdd014eef4c1612ef9474be7d708d46c2a2ce21","datavalue":{"value":{"entity-type":"item","numeric-id":1068110,"id":"Q1068110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$F06FA788-A36E-4C31-BC9F-3BFBAEC104FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65c468deacf9a7ac62a21f4655f39fd612630193","datavalue":{"value":{"entity-type":"item","numeric-id":1174132,"id":"Q1174132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$CC6A8DEC-D3BB-4B94-8099-D6EB9CD58C3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28d8eafc9a79890029b73b9b2b2eaf564379e3a8","datavalue":{"value":{"entity-type":"item","numeric-id":3672036,"id":"Q3672036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$267E13ED-AB7B-45F7-A492-7FC10AF305FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"026abbcd6b566d37afa5c1d0dbe1952b0978204d","datavalue":{"value":{"entity-type":"item","numeric-id":686246,"id":"Q686246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$A5EE1C0F-A84E-4317-B366-34A4EE207381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d20d43981ea8728a5c02a1bf60e0f2b91181b43","datavalue":{"value":{"entity-type":"item","numeric-id":788002,"id":"Q788002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$3EC05BF5-C8C2-4CC4-AE95-0349D0FF19C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1901aedd2d8549517a3f77a27b2a3787fa019529","datavalue":{"value":{"entity-type":"item","numeric-id":3731637,"id":"Q3731637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$FC717905-5D8A-4E85-B6EA-284BD9A2E281","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":"Q1962038$EAE8AA27-CD08-477F-B701-AA445DA6F63C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d60c9e7ebaed93a14c443423d2ee67e909f62ff4","datavalue":{"value":{"entity-type":"item","numeric-id":4368728,"id":"Q4368728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$5ABAA823-35AE-4EEF-A79A-BBB3AA6ED3F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"785e7851fac401f47fc66697d0bfc439f0b289a0","datavalue":{"value":{"entity-type":"item","numeric-id":4368729,"id":"Q4368729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$D9684470-B34C-4C7F-8A4E-A67DA0E508E5","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":"Q1962038$B2D1F825-00D6-45EB-8010-4B23183F91E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f3a345ac969991571213b2a34fe3bc06c137d18","datavalue":{"value":{"entity-type":"item","numeric-id":5896404,"id":"Q5896404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$26297315-421C-400A-9419-DE84012660A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef59647203c58ee1f83043f928eba109372c62e9","datavalue":{"value":{"entity-type":"item","numeric-id":1209148,"id":"Q1209148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$26EF9A33-456E-42FD-8BAE-7E387E12E1AA","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":"Q1962038$BB957B78-8706-4922-B456-202113F7E46B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df30420f3f06efdb09caaddc00c075a8d8f23edb","datavalue":{"value":{"entity-type":"item","numeric-id":287166,"id":"Q287166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$2AFC9ADE-FB44-4D1C-8067-1562EC86C8C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca6d57925534eab4e684d7cc70dcf457959b9e8","datavalue":{"value":{"entity-type":"item","numeric-id":4877526,"id":"Q4877526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$0C0050AC-DDC4-4391-B7EB-0B7AFC224F1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20b9c062c65fa50baeb0cadac82aad397e032bf","datavalue":{"value":{"entity-type":"item","numeric-id":3960122,"id":"Q3960122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962038$43DA7C9C-F421-4DA1-9993-47A5E64F974D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"5e09ce3bca37019cfda6b2f5b3ce9a763e7955b8","datavalue":{"value":"Q127343082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962038$D7221561-F049-4448-927C-3CBBF52DFEE0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9c4396f6952b1252a0c88f6eb371b9258c712a2","datavalue":{"value":{"entity-type":"item","numeric-id":5057448,"id":"Q5057448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ab69fb2d36d727db19689a19686a0c7eb1bc79a","datavalue":{"value":{"amount":"+0.8949739336967468","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":"Q1962038$B2F0AF5F-8064-423C-B3FA-BA8622F59E2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58379d1860d8f5f672edb21e8872d75a5486590a","datavalue":{"value":{"entity-type":"item","numeric-id":4268709,"id":"Q4268709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b683327b591eb7900198c4a4005a9c94d30bae1","datavalue":{"value":{"amount":"+0.8942792415618896","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":"Q1962038$F786D880-1390-4FB4-B1AA-98D71D2DAFD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"282490b906543e69d012cbb1488c27c2cf0f88d5","datavalue":{"value":{"entity-type":"item","numeric-id":4572004,"id":"Q4572004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b683327b591eb7900198c4a4005a9c94d30bae1","datavalue":{"value":{"amount":"+0.8942792415618896","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":"Q1962038$87E6ABC2-C853-4DF9-802F-DCA0477748E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5bdd1f4e6bfadf179d00b69e26358ac2b7890c9","datavalue":{"value":{"entity-type":"item","numeric-id":4645186,"id":"Q4645186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21add895dc51e568a1b16822ab681a2f249dd56b","datavalue":{"value":{"amount":"+0.8893482685089111","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":"Q1962038$AAA9D5F7-A95F-4C42-A619-27C759BDA986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b45204a3333a4f36ef0baf41cad7f2522cb6651","datavalue":{"value":{"entity-type":"item","numeric-id":5060107,"id":"Q5060107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"311a600ad646e0907e0eb0bf57cb2a0f6f5acd08","datavalue":{"value":{"amount":"+0.8849599361419678","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":"Q1962038$FAE9CA0C-9ECF-4F9A-B6A1-4788A0ECBE3B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1962038","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1962038"}}}}}