{"entities":{"Q476446":{"pageid":478213,"ns":120,"title":"Item:Q476446","lastrevid":52148006,"modified":"2026-01-21T01:01:50Z","type":"item","id":"Q476446","labels":{"en":{"language":"en","value":"Dominating induced matchings for \\(P_7\\)-free graphs in linear time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6375648"}},"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":"Q476446$0693D67F-E376-4B6F-B8E0-6E32849D57F0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"075790b921d2f98f4a79320d18cb191099920ad5","datavalue":{"value":{"text":"Dominating induced matchings for \\(P_7\\)-free graphs in linear time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q476446$7CC54D75-F624-4EA9-BC02-180B96696BA3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7ef9ce586bf7031e7b8895525d7f1485ea6c9660","datavalue":{"value":"1307.05171","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476446$BE40808C-9A60-4312-922F-BC01285CC40E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbb68d9de22321af7fb543db220c0a16a741857c","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$54C60BC6-6F61-474C-B2C8-F047DED13969","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1cf9debe45e382f5f77b3553301ae0391bc889d","datavalue":{"value":{"entity-type":"item","numeric-id":222633,"id":"Q222633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$2A6EAF12-514A-4587-9CFC-8A6689EA197F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$657943A5-5B83-4DA6-8432-3044771E1ADE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"73dfefec2f6ca5d698146ea0cb5593f631aa8cde","datavalue":{"value":{"time":"+2014-12-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q476446$C0171AF2-A4B0-42D7-BC9D-EF2AA8DD8847","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"83343b334476fc64f3a581774f9950625de71a98","datavalue":{"value":"A dominating induced matching (d.i.m.) is an induced matching that is at the same time a dominating edge set. The dominating induced matching problem (DIM) asks whether a given graph has a d.i.m. The DIM is NP-complete for very restricted graph classes, say for planar bipartite graph with maximum degree three. In this paper, an algorithm is designed that solves the weighted DIM problem (to find a minimum weight d.i.m.) for \\(P_7\\)-free graphs in linear time. The algorithm is robust in the sense that it either finds a minimum d.i.m. or finds out that the input graph has no d.i.m. or is not \\(P_7\\)-free. Along the way, a simple direct linear algorithm is given that recognizes \\(P_4\\)-free graphs (alias cographs) with d.i.m. It remains open whether for some \\(k\\) the DIM problem is NP-complete for \\(P_k\\)-free graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q476446$27D32FC2-59F5-4E3D-AFD8-0B1737C05F76","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b88ad96d2db1885238a8b67b25b8706a183b2b40","datavalue":{"value":{"entity-type":"item","numeric-id":251101,"id":"Q251101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$72F5679D-EE0B-4440-9A8F-BDE9AB9B9931","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476446$D6979125-250F-48C7-8F87-CCC552F7D9E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476446$C2C5BB21-5BF0-4753-947D-9438A2CEDA35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476446$D02BDEDC-093B-4727-8FAE-D2AC352EF918","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c9443da64efe1bf4aaee19725f85dcd0d6a615d5","datavalue":{"value":"6375648","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476446$D40CE743-2596-4732-9052-F5025D71173A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd9b2d3af165d0e99d060eb25d738122f976f5f2","datavalue":{"value":"dominating induced matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q476446$6CFCD416-393F-4458-9E8E-6EBE4668EC0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4080d4779d6ba38d38a2239f11a9d17556f6234","datavalue":{"value":"efficient edge domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q476446$3CC849C2-59A2-45C0-98E7-0D33B9E1971F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75108b8b8bcd70020941c6cfa5ad48f67fdf987e","datavalue":{"value":"\\(P_7\\)-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q476446$1BB0F66F-1196-4E08-A77F-54C72DF3F61E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q476446$61366853-E46E-4908-A44F-A95976FB28C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9d58dd99c100180c7f263d214d964585abb5a20","datavalue":{"value":"robust algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q476446$41679E78-DCCF-406C-B2F0-F492BC779A29","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":"Q476446$5335FE42-01CC-4DE2-92E3-22BCF4D8DCA5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b02e4307ae084592353fa5986f3c311498ac475a","datavalue":{"value":"https://doi.org/10.1007/s00453-012-9709-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q476446$6E263EA4-53C1-44F2-9186-6C21284DC251","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a69f3285da09ce4959a812be68cb407e9fee2386","datavalue":{"value":"W2444140751","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476446$4559B206-CFF0-4526-BF0C-EA9BA499CF5F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$5D9B32A5-2D97-4A67-8FDA-53A419036125","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f12af41ed187d70b4f8551c0debc8584dce55dda","datavalue":{"value":{"entity-type":"item","numeric-id":1084114,"id":"Q1084114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$7F91A5A8-6208-4449-B14F-72B9BF06B997","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08cf5fdb48dc960a72a89faf0ec5b9a25ba31b22","datavalue":{"value":{"entity-type":"item","numeric-id":817767,"id":"Q817767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$F328A415-9DF8-4AAF-B141-06B5E2F52032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42e05233e050b0618649efbb512daa97eb8c5c5d","datavalue":{"value":{"entity-type":"item","numeric-id":3557057,"id":"Q3557057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$680B3080-5D14-4C48-AD65-7AA3D0E5E039","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1db8b8ced0c6ffc2b675cd7438bfaaefa3547537","datavalue":{"value":{"entity-type":"item","numeric-id":1764802,"id":"Q1764802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$ECCDEBDE-F7C1-4BF2-9152-3A722B05F2E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cbdc2188619a17911fbd34af2a3359e70527560","datavalue":{"value":{"entity-type":"item","numeric-id":1764808,"id":"Q1764808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$39333283-8E6C-4209-8C32-2B54BAFE41C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b53d6ed16a94a54ef4bb9087bb7261d618cf3cc","datavalue":{"value":{"entity-type":"item","numeric-id":4909544,"id":"Q4909544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$0BFF8BCC-9FC0-44F7-923E-62A46719F5A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d49994886367f3cc3aff4b4111a4922dd7bcd58","datavalue":{"value":{"entity-type":"item","numeric-id":3648499,"id":"Q3648499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$B7427643-B7CA-4C04-B001-945B708FD8AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2814d366c2d85301cc0357be8472011b8ea6f0c5","datavalue":{"value":{"entity-type":"item","numeric-id":716179,"id":"Q716179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$5BF2A614-34A6-492F-A290-0CC76D978E93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f590ec33a5e4d01bbe007cfbdedf6a8e5d82e33","datavalue":{"value":{"entity-type":"item","numeric-id":3655141,"id":"Q3655141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$293BDEA1-3D0D-4270-85AE-09F29BB556AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3edc2fe01664e7ae5dbedc60a81011b311142a1b","datavalue":{"value":{"entity-type":"item","numeric-id":3694709,"id":"Q3694709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$6A1218DE-E765-468D-A589-B9F4FF34BABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8fe56184955dbba620e4cb94dc309dfe37fcc19","datavalue":{"value":{"entity-type":"item","numeric-id":1974445,"id":"Q1974445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$897E7ED8-5453-41B7-8FEE-638E0A3C739A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"291f43b3c3314deaee3a1b29096a4461fb8e8bb7","datavalue":{"value":{"entity-type":"item","numeric-id":5249049,"id":"Q5249049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$8E086F55-7983-4FB8-8F16-CBB6C26C48D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9475b7e249a6d6113efb911086405b8e1670a1ec","datavalue":{"value":{"entity-type":"item","numeric-id":1313728,"id":"Q1313728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$51A0CF61-29F6-4B36-BB4A-FA2301D39DA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b44897b7d36b48c7d487f1af70f89fbef7a74cb","datavalue":{"value":{"entity-type":"item","numeric-id":1613347,"id":"Q1613347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$558BF129-3476-46FB-BF43-86C13355C311","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e405b7fbda3f49c85188dd1e8eaf0b9f0a8ade2b","datavalue":{"value":{"entity-type":"item","numeric-id":1301738,"id":"Q1301738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$5BA81D35-F3ED-438A-81D3-89199C0508B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69f254905ff1ada4c9ba698b1b0da28d301a3fb7","datavalue":{"value":{"entity-type":"item","numeric-id":1396949,"id":"Q1396949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q476446$1E6360B5-E79B-47BF-8145-A5FC1B1E510D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6b701b5d686161d7b8c824d2a5f1b678aed7c3fb","datavalue":{"value":"10.1007/S00453-012-9709-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q476446$9C392320-EC59-43C3-8F70-B958FE2D969C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05d69a5d8a3b72bee3b0696bd64b44660e974b73","datavalue":{"value":{"entity-type":"item","numeric-id":3104604,"id":"Q3104604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e193fe7773f9545c2f28cb02feff499de8af881e","datavalue":{"value":{"amount":"+0.9971408247947692","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":"Q476446$6BA0339E-3DB7-4455-A2ED-86F83DFD489A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afe2dea375cf1d8e819467b4cbde14ff8890b999","datavalue":{"value":{"entity-type":"item","numeric-id":524382,"id":"Q524382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"587fd72666424aa30152c46d68134f6413645017","datavalue":{"value":{"amount":"+0.9323463439941406","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":"Q476446$68426C3A-EA34-43D0-830F-EE37942A231D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3f80addcfdeb0e3d1ec9376ccd30f269a589571","datavalue":{"value":{"entity-type":"item","numeric-id":2192098,"id":"Q2192098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12b59b2e0b916dbac47e1b33b75b3f7e639499b3","datavalue":{"value":{"amount":"+0.8954078555107117","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":"Q476446$760B51BE-4BEB-4C21-9BB4-AA429B8EB9D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce45eef621e6d7e060100611feccd60affcd163a","datavalue":{"value":{"entity-type":"item","numeric-id":777392,"id":"Q777392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e6b23cdefda43ae6999e0d2998bd8a213380e80","datavalue":{"value":{"amount":"+0.8924450278282166","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":"Q476446$76F8397D-1F69-4161-8536-B69A335C1EE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8aa50b268227659be4836fe0c9b4ec7c90a3a256","datavalue":{"value":{"entity-type":"item","numeric-id":2158196,"id":"Q2158196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4d8de70a42ae78030174fa4eab0d85094d0743b","datavalue":{"value":{"amount":"+0.8921414017677307","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":"Q476446$35364EA8-7580-47BD-BC92-B204ED41118C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:476446","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:476446"}}}}}