{"entities":{"Q5937917":{"pageid":8114719,"ns":120,"title":"Item:Q5937917","lastrevid":47642293,"modified":"2026-01-02T07:16:33Z","type":"item","id":"Q5937917","labels":{"en":{"language":"en","value":"Efficient algorithms for graphs with few \\(P_4\\)'s"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1621226"}},"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":"Q5937917$4DA19BB2-1317-4059-9654-257FDC2037CF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d1c167582b8d99221fe81b854d970e531abaac1c","datavalue":{"value":{"text":"Efficient algorithms for graphs with few \\(P_4\\)'s","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5937917$CEF1E655-05BA-4B31-B514-6479EF53323B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cabac742d8523a4fc3b5928a152eecf7e5f1389c","datavalue":{"value":"0980.05045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937917$8A1DF496-4CDC-42EC-80F1-84C3E28090B8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b18a1949ec6141a91370b0109221be6e44903ec7","datavalue":{"value":"10.1016/S0012-365X(00)00258-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937917$78E3B429-68C0-4789-83D0-B930DE44D7D6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"206b3ec8cbaf149080c58314ec18c3b633966649","datavalue":{"value":{"entity-type":"item","numeric-id":190504,"id":"Q190504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937917$4DFBE483-C64A-4914-87F9-71CD332054F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d8e7715a2f78d23e9e49bdcad66cde6bee1dec62","datavalue":{"value":{"entity-type":"item","numeric-id":190505,"id":"Q190505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937917$8512D9F4-FC85-4848-990E-CBF141B9357E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9034d743abb2e8189da1fd67afac14b0cf3088f3","datavalue":{"value":{"entity-type":"item","numeric-id":175587,"id":"Q175587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937917$B49598D0-5238-4331-9C76-BFF95696B45B","rank":"normal"},{"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":"Q5937917$3ED1A802-4FB2-47B6-83AF-E4586F81DD36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d838f189c5dee0252f326bcac58fa27d9924b24e","datavalue":{"value":{"entity-type":"item","numeric-id":190507,"id":"Q190507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937917$B3E257C6-1F5E-46E7-9519-E1E157E71CF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e7020a54266d4b2ab3b7f83a2814036c1ab56ec","datavalue":{"value":{"entity-type":"item","numeric-id":185063,"id":"Q185063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937917$0C3FE6E7-EF28-4FA9-952A-52F6C179FC68","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937917$2546A77A-A010-447C-A93E-1768E954C21B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"740d9e7b5ed53dada835ed8dd1fea829801958aa","datavalue":{"value":{"time":"+2001-07-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5937917$B802471A-ABB4-4EF0-A41C-B5518328EA59","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2a7283772ef8ba13170ecd0407b7788402263a01","datavalue":{"value":"A graph is called \\((q,t)\\)-graph if no set of at most \\(q\\) vertices induces more than \\(t\\) distinct \\(P_4\\)'s. The authors show that many NP-complete problems can be solved efficiently for graphs with ``few'' \\(P_4\\)'s. They consider domination problems (domination, total domination, independent domination, connected domination and dominating clique), the Steiner tree problem, the vertex ranking problem, the pathwidth problem, the path cover number problem, the Hamiltonian circuit problem, the list coloring problem and the precoloring extension problem. They show that all these problems can be solved in linear time for the class of \\((q,q-4)\\)-graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937917$F806E710-1A98-48F2-BD6D-92926E22389C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937917$817FBBE7-BEC5-4671-BF28-214BC8531C52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937917$F4A6E372-28CC-4C83-9875-4ADCED465087","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937917$067BF7E4-9904-4A99-8E32-ED28A6C35115","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937917$C60B41D9-5B29-44C1-8899-9B1ECEFFDD10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937917$99039799-C31D-4EA9-8A92-98907C54C6AA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"886227e92e395b4e0765f46019a01a6ed47af951","datavalue":{"value":"1621226","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937917$879F86AF-6BCF-4977-930D-96177A986ACD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8c9e80036612c21ad2ec3b6579e3228fd2ea1e","datavalue":{"value":"NP-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937917$CC36B7B9-BE56-4B61-BEED-5069FE402230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f607710e1bcd8426818fbf0effed996082aed3f","datavalue":{"value":"domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937917$E51E9921-7CE3-4EC1-810B-FD4DB5FA566F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b18d3948a42c7d1148336fe0006df600e3e0034b","datavalue":{"value":"Steiner tree problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937917$933F4256-A74E-4253-98C4-F6B43CD8C932","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"12f369260896ad84ac09aace07d3d64a29b7a7ae","datavalue":{"value":"vertex ranking","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937917$59A118E3-0C79-4FC8-9560-933D11276DE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67f458d393b772a7cf36a53976d2b5be911e683d","datavalue":{"value":"pathwidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937917$1C318C15-9D69-4A0D-9721-062AB9DDCC0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cee76cd8ac8ea1dad359ce1353cf422d465b2021","datavalue":{"value":"Hamiltonian circuit problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937917$A6EFF4CA-52B1-4AC1-92C9-EAA9DBA85A90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937917$44CCAC9F-5B67-453F-8A1E-2B37038E2EFE","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":"Q5937917$70982659-8EE7-4E0D-BE2B-369AAF6FC19A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d69692c80ea1c8767e05f6238ca6c2014dd21eab","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00258-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q5937917$ABC8C804-F828-4B90-A71C-5E20A1F44B30","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eb90bfab2bf6503a16af5601f0c902fee9fe52bf","datavalue":{"value":"W2062287043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937917$7939C12F-06E5-454E-96E5-72A8BBF543C9","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"bd08b952d88ee86132d726849c0d2efc0315c64a","datavalue":{"value":"Q128109451","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937917$62FC7856-CCA6-4E1A-9C25-653D58B2CAED","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"962b3e2734994d6c328a8b21e94d1e6325e20cbc","datavalue":{"value":{"entity-type":"item","numeric-id":4232800,"id":"Q4232800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1beb05ff2173127cba4e889d9d5df344002e7dc","datavalue":{"value":{"amount":"+0.838559091091156","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":"Q5937917$68050F3C-3004-4639-9F31-4B1045FB5FCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6961a4e297a0893ccd6c8790c9eec945684ea6b","datavalue":{"value":{"entity-type":"item","numeric-id":5248994,"id":"Q5248994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"420aaa1685b54dd2dd9f96bf7941f249746347d1","datavalue":{"value":{"amount":"+0.8239654302597046","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":"Q5937917$458B5265-2680-4FB3-A98D-59F4806B2A77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74d8ae4418494549fc9561bc21f19e211b578396","datavalue":{"value":{"entity-type":"item","numeric-id":1392556,"id":"Q1392556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c214519528861850b1b76bcfd6f09486adb0daa","datavalue":{"value":{"amount":"+0.8159601092338562","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":"Q5937917$B97C0F8B-C9D5-4B7C-A80B-EBC566DFBB8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0960f271537ea818ff41b437c2f736966bccd832","datavalue":{"value":{"entity-type":"item","numeric-id":2840684,"id":"Q2840684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d8d6ff35b0fdad95c48b79b72226188bca62489","datavalue":{"value":{"amount":"+0.8156817555427551","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":"Q5937917$FA83F0CB-65FA-47A2-BB9B-0BEDD0AB8B9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea781d2b4b1b63c6e4ca66c22f288eb84ac9821f","datavalue":{"value":{"entity-type":"item","numeric-id":1897361,"id":"Q1897361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6cf97821f52c3679109f5cf16059c67821db8bac","datavalue":{"value":{"amount":"+0.8127315044403076","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":"Q5937917$D807517F-B068-4BE7-A294-FCE3347E3C57","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5937917","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5937917"}}}}}