{"entities":{"Q7002657":{"pageid":21518919,"ns":120,"title":"Item:Q7002657","lastrevid":101370425,"modified":"2026-06-06T01:00:55Z","type":"item","id":"Q7002657","labels":{"en":{"language":"en","value":"Solving NP-hard problems on \\textsc{GaTEx} graphs: linear-time algorithms for perfect orderings, cliques, colorings, and independent sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8022170"}},"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":"Q7002657$9CE782C7-2EF1-4676-BB79-7D4C32C802B4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aa5688976523c348e7abb7c12377af3c3706f2c9","datavalue":{"value":{"text":"Solving NP-hard problems on \\textsc{GaTEx} graphs: linear-time algorithms for perfect orderings, cliques, colorings, and independent sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7002657$948038AF-310B-4E32-85A2-AE2397D1796E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a6f9c94f3c23aa7fcce7d46d373ba42265ded223","datavalue":{"value":"10.1016/J.TCS.2025.115157","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7002657$A4EAFB85-E3A9-446A-AC23-399920086F25","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f0bf7e5ea950435b1869b59f5448c7d19137c33","datavalue":{"value":{"entity-type":"item","numeric-id":340607,"id":"Q340607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$3052D01A-B60E-4EDA-8BD8-D435735A3F30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d8ea2c447cd0c607dca2e0941838d0bdc913e5f","datavalue":{"value":{"entity-type":"item","numeric-id":1702120,"id":"Q1702120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$006898F6-0A4F-4D67-84E8-56DEEE637B64","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$43634193-EBA9-4088-A6D5-E5C2093CD807","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2e6932eced7a8e5ec128f3e4abcdda6901995d2a","datavalue":{"value":{"time":"+2025-04-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7002657$67CB1965-F03A-448E-89AE-807485EDB957","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6b06841802a5e0a746dde7b60105fb9fd20ce46f","datavalue":{"value":"Cographs are a well-studied class of graphs on which many classical graph optimization problems, such as finding a maximum clique, maximum independent set or the chromatic number, may be solved by a linear-time algorithm. A graph is a cograph if it is either a single vertex or may be formed by taking the disjoint union or join of cographs. It is straightforward to see that a cograph may be described by a rooted tree in which the leaves correspond to vertices of the cograph and each non-leaf is labelled either \\(0\\) or \\(1\\) to describe either a disjoint union or a join of the subtrees of which it is the root.\\N\\NIn the present paper the authors construct algorithms running in time \\(O(|V|+|E|)\\) on \\textsc{GaTEx} (galled-tree explainable) graphs, a class which strictly includes cographs. This class is derived from cographs by replacing the requirement that they are described by a rooted tree to being described by a directed galled tree. These are graphs obtained from trees in which some vertices have been `galled' or identified to create cycles in a restricted way. More precisely a \\textit{galled tree} is a directed acyclic graph with a unique source in which every \\(2\\)-connected component of the underlying undirected graph is a cycle.\\N\\NThe authors give algorithms for \\textsc{GaTEx} graphs to find a perfect order of the vertices (i.e., a total order which may be followed by a greedy algorithm to properly vertex colour every induced subgraph), and to determine an optimal proper vertex colouring, a maximum clique and a maximum independent set.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7002657$E9A1605A-7228-4129-BD5D-74386A8999D5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"aef7566e0971cb09d580a31ad765a101a946a199","datavalue":{"value":{"entity-type":"item","numeric-id":412351,"id":"Q412351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$10794AE1-D4CF-4FE1-8F78-01FEB0EBD03C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7002657$B3809C5A-BE4C-4FCA-B960-760B0625990C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7002657$1342B280-26A8-47A6-B77C-61BB5D157F79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7002657$E5B70457-C963-453F-B878-FBD45776BDD6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b613ef8fa480611d70e21bb3d8c012277df2e89e","datavalue":{"value":"8022170","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7002657$2D60FF54-87A1-4931-B4A8-DB97C313D500","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"325045ab534bab8033fe49f49b77dd6b010db3e8","datavalue":{"value":"galled tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q7002657$73740FBF-6487-40A0-B0C1-0EE9C808D65E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99974e488eefe65e9a359b970a995a9b6d33d8e8","datavalue":{"value":"NP-hard problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q7002657$11017A1F-2E1F-4889-92A8-5B1B7DB85160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7250963987d7e4c99272889381793742a1498efc","datavalue":{"value":"linear-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q7002657$CBA909CE-632D-4E3B-8AC5-62F8346820D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ae14706edea88a102ee43da4032c363bf1c64c9","datavalue":{"value":"cograph","type":"string"},"datatype":"string"},"type":"statement","id":"Q7002657$4DB41DE7-E86D-41AF-B5F0-EDADBB731425","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1adb1579ecb6bb9aaca40d9ceb17f3584d731fa","datavalue":{"value":"modular decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q7002657$A4DB7D2E-AE1B-4139-98C8-BFA58F310A09","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":"Q7002657$C84F464D-E94F-4208-8A34-B8CE83D7773F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f2ed9d8a8413ac6991e3490a2859e032cc1ce46","datavalue":{"value":{"entity-type":"item","numeric-id":1272801,"id":"Q1272801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$5FBC4A26-BEC3-4888-9D56-91345B216AD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9bd269295ba877c106cd58908caf0f087a4411b","datavalue":{"value":{"entity-type":"item","numeric-id":3347930,"id":"Q3347930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$685C7041-92BE-4303-9838-C3E1FADC5900","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$6AF53E6A-2A7F-4089-87F2-2CB0FE632789","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":"Q7002657$1C845739-170D-4BA0-A79C-693A4C563E7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bd9545135d8eb802bd4c19148d6cda41510d602","datavalue":{"value":{"entity-type":"item","numeric-id":2775895,"id":"Q2775895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$C3DF213F-12A9-4DF3-914D-FA18BB1966CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"336f2275d018fd4c1f2e835dff5ad098beff6c7f","datavalue":{"value":{"entity-type":"item","numeric-id":913822,"id":"Q913822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$62AE80C2-F103-44B9-A147-010060501620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08d2c2bbc2c22ca26c4352e74dae4241ac242c99","datavalue":{"value":{"entity-type":"item","numeric-id":913823,"id":"Q913823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$9F609A78-0946-43AE-89AE-1FE29568117C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51c827a3a1264109f44fd38b700683669b8231c5","datavalue":{"value":{"entity-type":"item","numeric-id":4285914,"id":"Q4285914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$EA4D6E84-922E-472D-A0D8-6C3AFF3C3884","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":"Q7002657$EB0D17BD-F814-4DDB-9D0C-A05EE02EA292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93ad84d0a1a74f90cb7eae653f4eece82f4d2372","datavalue":{"value":{"entity-type":"item","numeric-id":458504,"id":"Q458504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$9F06FB01-14A5-4AE0-A7FA-467EC746D212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31a48d6b48d9fc7cfffb299dfa815b9b65d3a6ec","datavalue":{"value":{"entity-type":"item","numeric-id":5121555,"id":"Q5121555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$38BCF688-DB33-4737-95B9-C14DDE054446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c615367e5ba6507044f74e7d285437d338a932c7","datavalue":{"value":{"entity-type":"item","numeric-id":2172401,"id":"Q2172401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$AC7BD86F-BD89-430C-8C1A-D563ABB06395","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a06277d42bbb64eebf32af4178ae6a89dee7116","datavalue":{"value":{"entity-type":"item","numeric-id":6591462,"id":"Q6591462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$703D52D8-F8C0-4C5D-BD0A-5AD06A73537A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7b5cf38523e2d93bb511b7180bfff967a8279ea","datavalue":{"value":{"entity-type":"item","numeric-id":6180640,"id":"Q6180640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$86A8EFAA-7212-48DB-97B8-E366D1FDEF3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"653e08ca54575143db1448a96d42ad6e985cc80f","datavalue":{"value":{"entity-type":"item","numeric-id":2014353,"id":"Q2014353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$0BB938B5-948E-4201-A292-435F45D3BC73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d4bc5cdccdb5d9973204651de8ef54eb258310b","datavalue":{"value":{"entity-type":"item","numeric-id":1702121,"id":"Q1702121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$AD4EEDEE-D317-4CCB-9354-12FA5282A226","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":"Q7002657$9A74D128-8A60-4AD2-B997-0F2C687DF08A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26b962d5ada8b5bb3c241cecf1e141991f1d8c34","datavalue":{"value":{"entity-type":"item","numeric-id":918707,"id":"Q918707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$9FD4508C-95C3-4BE0-AF85-2601731F46F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"202b9eb5502a9e6d937cd593d23f4123081f0bbf","datavalue":{"value":{"entity-type":"item","numeric-id":3521955,"id":"Q3521955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$8E1B415F-9499-4459-9EDE-2F24781D10E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7299424584500685e44b40ee8dcd25ffd3b2f1bc","datavalue":{"value":{"entity-type":"item","numeric-id":5892162,"id":"Q5892162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7002657$0556E835-F2F1-408E-9156-AA6D4FB3108E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:7002657","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:7002657"}}}}}