{"entities":{"Q816574":{"pageid":818422,"ns":120,"title":"Item:Q816574","lastrevid":64555473,"modified":"2026-04-11T20:40:33Z","type":"item","id":"Q816574","labels":{"en":{"language":"en","value":"Polynomial algorithms for kernels in comparability, permutation and \\(P_4\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5010470"}},"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":"Q816574$89419D38-14D1-4F65-914F-9F371D514F00","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4ac1b1d0db912e81b0c357d9f775ff4e46dd6e49","datavalue":{"value":{"text":"Polynomial algorithms for kernels in comparability, permutation and \\(P_4\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q816574$4CDD87BB-F10F-4AD5-9330-032D3A9F6069","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6259556aa123a884ceb5d2398ce3e26710b31740","datavalue":{"value":"1083.05021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q816574$DF524414-94F3-4757-A78B-8FABEB7C3FBB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c1df01f0d88660a80678447d2b8f6079186def5e","datavalue":{"value":{"entity-type":"item","numeric-id":816572,"id":"Q816572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q816574$F9E961A6-D4E3-4091-BFAE-FCF79BE55B7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e3901454e8baf0ad608ae673c22343782ad2a1b","datavalue":{"value":{"entity-type":"item","numeric-id":816573,"id":"Q816573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q816574$0D8549C8-8F33-4BA8-A79B-C4619CA9FBD4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"d92a8df68dd721ea0fb0b324d32219435ae70dcc","datavalue":{"value":{"entity-type":"item","numeric-id":262441,"id":"Q262441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q816574$F977AE27-B698-4517-B042-9C35818B1344","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e48254e7cca8b756082b12a9577d73a3c911d8a0","datavalue":{"value":{"time":"+2006-03-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q816574$637813C7-9497-4AAA-A93A-527EEACFCF58","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3d1d2fb789585bd3c006dcc86044bf4406840499","datavalue":{"value":"A kernel in a digraph \\(D=(V,A)\\) is a set \\(N\\subseteq V\\) that is absorbing (for every \\(u\\in V\\setminus N\\) there is some \\(v\\in N\\) with \\((u,v)\\in A\\)) and independent (\\((u,v)\\not\\in A\\) for all \\(u,v\\in N\\)). The authors describe polynomial time algorithms for finding kernels in orientations of certain graphs where they consider the digraph \\(D=(V,A)\\) to be an orientation of the graph \\(G=(V,E)\\) if \\(\\{ (u,v),(v,u)\\}\\cap A\\not=\\emptyset\\) if and only if \\(uv\\in E\\) for \\(u,v\\in V\\). Analysing Champetier's proof of the existence of kernels in Meyniel orientations (orientations where every triangle has two symmetric arcs) of comparability graphs they show how to find such a kernel in \\(O(| V| ^2| E| )\\) time. For permutation graphs they consider normal orientations (orientations where every clique has a sink) and prove that a kernel can be found also in \\(O(| V| ^2| E| )\\) time. Finally, for \\(P_4\\)-free graphs which are special permutation graphs they improve this running time to \\(O(| V| | E| )\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q816574$4322D0A1-7454-4DBA-99FD-A96B932C714A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c21cb54e7c2c469712a9307e52fa5ab7414ba5da","datavalue":{"value":{"entity-type":"item","numeric-id":186196,"id":"Q186196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q816574$0611F9D0-8ADE-4E29-B610-2AF39699CF1E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q816574$DC275FD5-0695-4B78-9FF4-F5463C85B0AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q816574$7058AF96-C3EB-4B56-AD1F-1DD66A7CCBCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q816574$3B50F1EC-1023-4A29-ACD2-8029C46A1D92","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d9641c7259c2b54ab3cdceb524675c193d4cf2f","datavalue":{"value":"5010470","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q816574$481964D2-263A-491E-ACE6-83052287B2AC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"100beb8397f05d46f12f9c99001633652b89764d","datavalue":{"value":"Meyniel orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q816574$276FB153-343D-41F5-B871-FAAF684DC395","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c546a74a1ef42cc94175b55a898f3078481a659","datavalue":{"value":"normal orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q816574$E8AE3992-2929-4759-982F-1F48AE1CC1A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q816574$BBF65669-FDF9-43C6-963F-C5B22CB9EEB5","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":"Q816574$50E2AED3-E217-465D-96FE-2F3BCC9AF6B8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3ad7b2f45970650bbe213b4205baae1251b3d019","datavalue":{"value":"https://doi.org/10.1007/s10288-005-0067-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q816574$96FFD330-40EF-4BEB-8079-E85C3A3F2C9A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"65cbdec668ad7e8c47eeb040fd78bff00a0eba6b","datavalue":{"value":"W2077380800","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q816574$7FFDA5B1-795D-4EC5-90D5-5F1DB9E2486E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"45e9d7b7cb6798352d5d7b32d260666ee1f1bd76","datavalue":{"value":"10.1007/S10288-005-0067-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q816574$92EFFA02-2036-4D05-B14E-465D235C3232","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1afbf03bfec54a92c48773dfb5d575195870cb89","datavalue":{"value":{"entity-type":"item","numeric-id":2283107,"id":"Q2283107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18af29d4cdd4452c1178a945ececc0fda763fc9a","datavalue":{"value":{"amount":"+0.8337703347206116","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":"Q816574$DCD12966-E8FA-46DC-8E61-DA6266C33E8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bcdaded8a8128b2faf1f9383db5db12e1a58068","datavalue":{"value":{"entity-type":"item","numeric-id":1823257,"id":"Q1823257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64f68e73bf1b0621bf9a039e59752bd668904b77","datavalue":{"value":{"amount":"+0.7990221381187439","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":"Q816574$347F44B3-523C-4E7B-BBD8-711BB7027B4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12323073746e9b518d7b88cd758e71271f105430","datavalue":{"value":{"entity-type":"item","numeric-id":2485283,"id":"Q2485283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e52e28e2dddcc2165076fe91c224a781c93fec7f","datavalue":{"value":{"amount":"+0.7793816328048706","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":"Q816574$42B0404F-0DEA-4BFE-9527-6FC097C86213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2eb624b558bb1468a8cbeba96ebfb09ca3d6dbd","datavalue":{"value":{"entity-type":"item","numeric-id":3186539,"id":"Q3186539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bf8550ba7a2e09aa8dcc49291e507f12f4b3f9b","datavalue":{"value":{"amount":"+0.777275562286377","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":"Q816574$ACB785F2-48E8-4E36-9D3F-1D5D4EEBFC00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d999ef7d05281266a0cbc0a373e774323072cbbb","datavalue":{"value":{"entity-type":"item","numeric-id":3452029,"id":"Q3452029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c83cd1014352945ba1ba0c22b8c5b4a1e9ae29b5","datavalue":{"value":{"amount":"+0.7746884822845459","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":"Q816574$173F16AE-B8A7-4022-A111-798CDC85682D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polynomial algorithms for kernels in comparability, permutation and \\(P 4\\)-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Polynomial_algorithms_for_kernels_in_comparability,_permutation_and_%5C(P_4%5C)-free_graphs"}}}}}