{"entities":{"Q1283807":{"pageid":1294557,"ns":120,"title":"Item:Q1283807","lastrevid":70575768,"modified":"2026-04-13T15:33:19Z","type":"item","id":"Q1283807","labels":{"en":{"language":"en","value":"Construction of a simple elimination scheme for a chordal comparability graph in linear time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1271080"}},"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":"Q1283807$D6E1FD0B-BC22-4BC6-8F11-97122BA39C90","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"463720b167ba01f7ddbf7911ee4cd1b27159c236","datavalue":{"value":{"text":"Construction of a simple elimination scheme for a chordal comparability graph in linear time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1283807$9078A128-7418-4A52-8219-5724A221F5FB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9e7480d847de9d000fcfa91a7de4bb5800a3f5b3","datavalue":{"value":"0924.05061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283807$BA978A84-4C1D-450C-8B27-3AA7E0519BC2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"84fbe07dba0fd9707c34c4574bc005c546dd7247","datavalue":{"value":"10.1016/S0166-218X(98)00137-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283807$45585DA4-3CE0-431F-8E7E-F98B52E81965","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7490a2122b3e58ba600665d40184a6d9984d77c5","datavalue":{"value":{"entity-type":"item","numeric-id":1283806,"id":"Q1283806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283807$5B0C0A0B-8713-488D-A4EA-42664C65F7D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ef8392e01c11e85b032ddf62d87088b822bd19a","datavalue":{"value":{"entity-type":"item","numeric-id":344852,"id":"Q344852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283807$32F5F1D1-D39C-404E-B47A-FD2C287B71B1","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":"Q1283807$92664B47-B491-4036-B20B-CF514DE46153","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"179b40780f93d89d986b6f1110abe8d9772f7f5c","datavalue":{"value":{"time":"+1999-11-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1283807$75E78E62-3AE7-4708-A092-8011ECAB804E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"84c7789c829a442b6dd6a427c78e6ac80116cc96","datavalue":{"value":"Chordal graphs and comparability graphs are two classic graph classes playing a crucial role in algorithmic graph theory of perfect graphs. It is easy to see that chordal comparability graphs are strongly chordal---an important subclass of chordal graphs---and thus have a simple elimination ordering. This paper shows how to find such an ordering of a given chordal comparability graph by using cardinality lexicographic breadth-first search. This implies a linear time algorithm for the maximum matching problem on those graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283807$7E396A9E-B0F2-42B2-89E4-DC59AB5230C8","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":"Q1283807$1C758766-BB0F-44F2-8CE5-EA11E940603B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283807$AB3E5E1B-5243-4480-B465-FDD70BF4213E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283807$D2F16CB3-5805-4DAC-AF71-75A843B71C85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283807$A4BE7041-F0C7-40AC-B5BF-9E15D2C4204D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4f474a21cfdb7d36ca8b846055b8ec3cbca1b0bc","datavalue":{"value":"1271080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283807$8876EAD2-D42B-4F29-8154-1F7158B8F8A2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283807$5B1BE7A7-9A22-4564-9984-40BE64212E6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ff173e55f7f50e27e9b10e2b2b91767c00eb950","datavalue":{"value":"chordal comparability graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283807$FDD271EC-FED6-4637-8B34-6245FEA2F0C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f52dfccb5482b04dc4d0b66f37bfd46b42aa4eb7","datavalue":{"value":"simple elimination ordering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283807$362F0712-85BB-4340-A033-BBE9F80B4B03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283807$8FC64EB4-2881-41AD-9C36-6BB7A9124F04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"950e56ac872de59b365efebcf74901eb0e9b181e","datavalue":{"value":"maximum matching problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1283807$0B116967-51D1-4AEB-A828-FF529A2FAD8E","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":"Q1283807$8BD78B2D-91DD-4A39-8D89-EC21BE05485D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cf6d510bbe3a927f32d195ff13825cfed860b57","datavalue":{"value":{"entity-type":"item","numeric-id":4373681,"id":"Q4373681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283807$1FCF53C2-FD21-4C02-970A-F17254385B46","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":"Q1283807$9C894D91-95E8-4505-B837-1E71EE5A01A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8539d1fcf3cff5fbb08dd6973662b887ad57892","datavalue":{"value":{"entity-type":"item","numeric-id":5534028,"id":"Q5534028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283807$3D4DDE71-1146-4CBB-8BB0-7A834BA7ABDF","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":"Q1283807$8AC07D3D-8E56-4D49-B83F-184E96CB1280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7afdc016113a64b0d496c0b644cc26ec07b94627","datavalue":{"value":{"entity-type":"item","numeric-id":4229420,"id":"Q4229420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283807$83089252-B363-4A05-8110-EF11203CC23B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dc770be7fda211a08f36290a5d12cf41e7dc2c4","datavalue":{"value":{"entity-type":"item","numeric-id":1803661,"id":"Q1803661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283807$4E50A558-622B-4D4F-9F95-D4423895C41D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8be35524e11c7a2d4316bee13fb4842a08031a59","datavalue":{"value":{"entity-type":"item","numeric-id":1066918,"id":"Q1066918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283807$A1DB0925-FE56-47B6-B138-E0958AC383C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ab432e61cac0d257217a8aaa345087b6099b173","datavalue":{"value":{"entity-type":"item","numeric-id":1182042,"id":"Q1182042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283807$4A1C3558-8F4F-43E7-BDF8-B9E100F01604","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a2bbb8ad1f3589516fad98f1995bc229b7720f6","datavalue":{"value":{"entity-type":"item","numeric-id":5501778,"id":"Q5501778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283807$88C0439E-1301-4928-9D4F-73CDEA0E8D5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8592b19f12bd09556a4de81ad49778d747c4f77b","datavalue":{"value":{"entity-type":"item","numeric-id":4124209,"id":"Q4124209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1283807$B58991C4-D87E-4DC1-A722-C6408364A604","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b76a34e50277abd63556414d47c085e2a3bc0453","datavalue":{"value":"Q127065923","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1283807$3D13436F-4D1A-430E-AB84-0E0BD0EABA01","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1827f6051809597d2a751e36bc6b69cc821cf56","datavalue":{"value":{"entity-type":"item","numeric-id":972319,"id":"Q972319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"201fa6a8b3d1bca77ecd690f0c744eea26d237a4","datavalue":{"value":{"amount":"+0.92558336","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1283807$31B53EDB-A1BB-4D49-AADB-293238DE1343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90707394c8e11ac65c58723218bdfa240bd162c0","datavalue":{"value":{"entity-type":"item","numeric-id":3522954,"id":"Q3522954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ddf214d995c79621271d94c5b97645d2fccef3a","datavalue":{"value":{"amount":"+0.9230151","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1283807$3097F13E-D2BC-4EAD-8A6E-1CBD17EF379C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f2b094e11cf549df91be777a3d71dfe930ecab2","datavalue":{"value":{"entity-type":"item","numeric-id":1350607,"id":"Q1350607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d06980594a81f843f72c9c85648967abcfb4cbd2","datavalue":{"value":{"amount":"+0.9052669","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1283807$A3C368F2-E61A-4828-B61D-464098DCD289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c8f23a1fc4d61ded98b98429fd77c4479e9bd07","datavalue":{"value":{"entity-type":"item","numeric-id":2839220,"id":"Q2839220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73345e5e42bf26d2341a598ee1e9c814615ea25d","datavalue":{"value":{"amount":"+0.8974076","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1283807$2AFE9CD0-AA00-4455-8E69-B3CAE3D7EB54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c64008400f037b702b35cb5d99cc2dd0137579b2","datavalue":{"value":{"entity-type":"item","numeric-id":4229420,"id":"Q4229420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"232a653f71840919ac308957826f5d3372c22b2b","datavalue":{"value":{"amount":"+0.8904915","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1283807$57134F57-8716-44B3-B7D0-FA3CCE0C90B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1478a6fee6dad8438b93c99e28b4fe32d38ca8f","datavalue":{"value":{"entity-type":"item","numeric-id":4737226,"id":"Q4737226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2d470503f88e0a46d0297fadc2a9e127a691675","datavalue":{"value":{"amount":"+0.8723004","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1283807$EE095139-B319-4752-819A-AB10BFF3182D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88753f2102bf910786ab55159a818fc751b45850","datavalue":{"value":{"entity-type":"item","numeric-id":497140,"id":"Q497140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f14f787686a04bd1c8eacde4c85e50f9d36868a","datavalue":{"value":{"amount":"+0.87061244","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1283807$1D607EBB-607B-4400-8DF2-14588D9CCFF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4234595b2c599f8051ee019443cb75b8d8acb556","datavalue":{"value":{"entity-type":"item","numeric-id":1195864,"id":"Q1195864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d63581909ee0c90907426282439e99b895d85c0","datavalue":{"value":{"amount":"+0.868522","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1283807$BDF21F9D-EAA4-496E-8DA9-F0D0D83E72D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f61c0059ca5a5ac6980fe1457115b70d4bda2a54","datavalue":{"value":{"entity-type":"item","numeric-id":3335007,"id":"Q3335007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f33a7c8dadc8db348cddd7115e7b11ad2547770d","datavalue":{"value":{"amount":"+0.86446583","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1283807$7362E974-5538-4376-A999-83F92E90F990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d79f961d06567838aefedf6558c25e7c17a378ae","datavalue":{"value":{"entity-type":"item","numeric-id":3481747,"id":"Q3481747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"481a30830556cbcd63e7b4991c55471a231f4d08","datavalue":{"value":{"amount":"+0.8637388","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1283807$E35AEB23-0DCC-49AA-8671-F9627EA48D3C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Construction of a simple elimination scheme for a chordal comparability graph in linear time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Construction_of_a_simple_elimination_scheme_for_a_chordal_comparability_graph_in_linear_time"}}}}}