{"entities":{"Q1962062":{"pageid":1972804,"ns":120,"title":"Item:Q1962062","lastrevid":47437336,"modified":"2026-01-01T18:17:03Z","type":"item","id":"Q1962062","labels":{"en":{"language":"en","value":"Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1395027"}},"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":"Q1962062$8943EBC6-69A5-4925-9B44-9A27899CAE38","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b4f516d1a40f87de23877b1634699e7f59adf0a6","datavalue":{"value":{"text":"Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1962062$9D252E6E-4760-4D3B-B3BE-B38DF8065A38","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c1a151200a8635eb756ca6cbb8811c822d287b4d","datavalue":{"value":"0960.05094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962062$AAC4C083-5D44-4518-82B2-5F532C04C4FC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0f6e08fcd9beb4ccbb2ccf7dda3c38564d1c8e83","datavalue":{"value":"10.1016/S0166-218X(99)00149-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962062$6DA22E61-0D8B-487F-9B63-C6999DCE85DE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"97dbd21a3cbf1118b1d651db6d325ca352db3dc3","datavalue":{"value":{"entity-type":"item","numeric-id":221665,"id":"Q221665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$4E579CC2-64DD-4C21-B564-AAF612AC181D","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":"Q1962062$F416EB3E-7BD0-4930-85F7-FE02CBECC15A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fae3664154dc61222a1003dc28228b6754c9eec5","datavalue":{"value":{"time":"+2001-05-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1962062$AB791262-9CB7-4064-BCCF-8AB76A280757","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cd1fc85e338305381be79ee859e2432ffc595354","datavalue":{"value":"For a graph \\(G = (V,E)\\) a linear ordering \\(\\sigma\\) of the vertices is called a strong ordering of \\(G\\) if the following property is fulfilled: if \\(ab, ac, bd \\in E\\), \\(a <_{\\sigma} d\\) and \\(b <_{\\sigma} c\\) then \\(cd \\in E\\). In this paper the author considers strongly orderable graphs, i.e.\\ graphs that admit a strong ordering of its vertices. Two new characterizations for this class of graphs are presented using elimination orderings on the vertices (quasi-simple elimination) and the edges (simplicial-edge-without-vertex elimination), respectively. These elimination orderings generalize characterizing elimination orderings for strongly chordal and chordal bipartite graphs. It is shown that a strong ordering of a strongly orderable graph can be found in \\(O(|V|+ |E|)|V|\\) time, leading to a \\(O(|V|+ |E|)|V|\\) time algorithm for recognizing strongly orderable graphs. Furthermore, the author proves that the class of strongly chordal graphs is properly contained in the class of weakly triangulated graphs that do not contain a sun as induced subgraph. Finally, greedy algorithms for computing minimum coloring, maximum clique, minimum clique partition, and maximum independent set on strongly orderable graphs are given, that run in linear time, provided a special strong ordering (lexicographic quasi-simple elimination ordering) is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962062$34A6DCD9-14FA-4803-A7DF-C103A186D162","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962062$D025F571-FA0B-4260-B6EA-3D8C6A29C63F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962062$584FB817-009B-452E-B3F0-026C155A8FE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962062$0F577EBA-0207-4E35-818A-8B5C638A0892","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4d87d3ac523abbb31e9630b721c5ae372a917921","datavalue":{"value":"1395027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962062$6E2DACC8-BAFF-4817-A278-ACA65DCD7E93","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ae5574b8601b3a3fc0f3d2b92ee5c9341f0ee4e","datavalue":{"value":"strongly chordal","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962062$9EAA3F7A-9DD6-4383-BAFC-1CDB39B1024C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a880d3518e40f0db33b07dbfa7debddb43762fb4","datavalue":{"value":"chordal bipartite","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962062$57422B53-9DBF-4103-B2E5-32DF756055AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7decde45aa28f7520212fb84cab816519940f4c9","datavalue":{"value":"recognition algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962062$FBB361F9-04A6-4000-A495-995F49449E9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962062$94AC2CF1-A9FE-45C2-BFD0-0FD4145A848D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00b378859afdb68c30844c3d745b6b412b44cbdd","datavalue":{"value":"elimination ordering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962062$BA37C479-8D88-4318-8063-1CCFFAE72077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b6fbaa665d2c2987e08bc6dbe57daa649ae0960","datavalue":{"value":"optimization algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962062$0DD6444E-DA58-49FA-AC45-192CB299050E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44a181c7b2997b4e3846dd20fd7f7cfe8269ff11","datavalue":{"value":"maximum clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962062$FEA0C4D5-B1BA-4EDB-8587-BA8F778D66B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b5e5336cab30e039ac622a0d2dff0f49409a421","datavalue":{"value":"minimum coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962062$9458E061-E107-40C9-935D-C9BA35B56BC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09ad26e0640eed49466fb447ea862f2bfe9272ea","datavalue":{"value":"strongly orderable graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962062$839555A0-4C58-4667-A039-B12B6B91EAB6","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":"Q1962062$A7D949FA-6F62-4F08-B9A4-5100BCF2800C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b717ce5476163967b0df9674233704df8f3864c4","datavalue":{"value":{"entity-type":"item","numeric-id":3344216,"id":"Q3344216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$6532697A-CD4A-4218-95DB-049B1459F95D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44fc750bc29c7ea3b2be952d54a16267cee2cbbf","datavalue":{"value":{"entity-type":"item","numeric-id":1117254,"id":"Q1117254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$F9F0C3E7-7744-4CAC-B8F0-F5E77435B35B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6b351fad9657df3efe83a4f8f8f50558953cda3","datavalue":{"value":{"entity-type":"item","numeric-id":3697054,"id":"Q3697054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$A2B13754-8CF0-4592-811D-F08DA1CE00E9","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":"Q1962062$6BFD3216-6617-4641-9164-216BF1C06594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f7a883b6ad108bd3e6989dffe32539fa4da99a7","datavalue":{"value":{"entity-type":"item","numeric-id":1392565,"id":"Q1392565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$7F8F964E-5DA4-4A0B-97F3-EF28854E2622","rank":"normal"},{"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":"Q1962062$761FF873-347A-41B5-BF9D-9E2BA516E351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6ba8beca23cdaad0ac4c8fdb9394466e17ade7f","datavalue":{"value":{"entity-type":"item","numeric-id":1051004,"id":"Q1051004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$CC59A2AB-DDDB-4BC7-9F8D-720AA47D79B2","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":"Q1962062$3D7E2A34-7E37-45E8-9A08-02A0A104D15F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c33959e8c3fbe7080f98305389592daf8f06321e","datavalue":{"value":{"entity-type":"item","numeric-id":5634016,"id":"Q5634016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$741C389A-DA1A-4B37-AD3C-7FFA9AA166ED","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":"Q1962062$8363BEB9-8117-4A3D-A221-4F785CBB9815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f41bc558acdabc32b8492268548c9e818697a7fa","datavalue":{"value":{"entity-type":"item","numeric-id":4198811,"id":"Q4198811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$B6FD5488-FAFF-4FAB-9B19-10250F5BF169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b276fdb2188dac0c4b19127d85e1049cb332b2c","datavalue":{"value":{"entity-type":"item","numeric-id":801088,"id":"Q801088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$16663F86-44BF-4A6A-AD38-9B88CF6CF29D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60e9b00fe16bc121f8312d916d237c3fe83869de","datavalue":{"value":{"entity-type":"item","numeric-id":672487,"id":"Q672487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$464989AF-CF84-4B3D-9674-E4B21BB55E28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd8097640b1f4ba9eec43837bd81d298e8358613","datavalue":{"value":{"entity-type":"item","numeric-id":810029,"id":"Q810029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$7367A90C-4123-4208-8A70-DB946417FBB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b3c99368ea38ef93edcc839b4081d214aa7efc0","datavalue":{"value":{"entity-type":"item","numeric-id":2553372,"id":"Q2553372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$C5BCF65A-8994-43C9-9139-892CF4F56D65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c774834971b086c761bf1be38a21a13366e3f9d","datavalue":{"value":{"entity-type":"item","numeric-id":3758873,"id":"Q3758873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$164F6A26-72AC-40AD-A979-B049B29B5C2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65fa25ecef461a83ce03679a7bacb00b33cb4090","datavalue":{"value":{"entity-type":"item","numeric-id":3801084,"id":"Q3801084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$FA61FFAC-6EAF-4BE4-9E9D-EAF850BFC6BE","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":"Q1962062$E7AC7ECC-A530-472C-AA1F-D6888DC83D28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92caee6160091f6ea9c8584bed842b317c3b9042","datavalue":{"value":{"entity-type":"item","numeric-id":2366069,"id":"Q2366069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$F8FED825-240E-4F2B-8F05-2913B6CC2C12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae9d006ba4b2d397812b9353164a360251d8f97e","datavalue":{"value":{"entity-type":"item","numeric-id":3701460,"id":"Q3701460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962062$F3CF29FB-7132-4774-AC7B-4480840A4104","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"567e41914cea7f92e99da72e224a5a77fba022f0","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00149-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1962062$AD09BA3B-D2C4-4FBA-A237-65BD273BD7DA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e3eb9ab27a52f26a0dfbd46cbae3b1881330b50f","datavalue":{"value":"W1994963913","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962062$F95C5924-41D1-42FF-B280-EC4CDB0384BA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"713f56918b0ffb60566f46e546e8d8eb3050fa3a","datavalue":{"value":{"entity-type":"item","numeric-id":4247270,"id":"Q4247270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9431a896cc365af99cb0cb84d5e7bf956ae32236","datavalue":{"value":{"amount":"+0.8666384220123291","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":"Q1962062$B28A851E-12BD-4360-8CE5-5BE6023ED7BA","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":"a8b030126328c236cc7a29ec2f82d1332d85d7cd","datavalue":{"value":{"amount":"+0.808183491230011","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":"Q1962062$D75E7ADE-9A94-49FC-A573-2CAE9D9BE6B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d8c413c288f39835d9df22e010023a6fd70d06a","datavalue":{"value":{"entity-type":"item","numeric-id":1815322,"id":"Q1815322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74bd2f30cbd07d5a7e3f9d32e6c7d975be3f2eb7","datavalue":{"value":{"amount":"+0.7831505537033081","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":"Q1962062$5A22DE58-1C9B-4A80-88DC-63303E454B4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"476f62253c649059c23eb18f6f560c72039009eb","datavalue":{"value":{"entity-type":"item","numeric-id":1584312,"id":"Q1584312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74bd2f30cbd07d5a7e3f9d32e6c7d975be3f2eb7","datavalue":{"value":{"amount":"+0.7831505537033081","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":"Q1962062$08F81875-6D04-4258-9AB2-C2B371503950","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8b5817a1a58b871578bc06d6363b498af73d03a","datavalue":{"value":{"entity-type":"item","numeric-id":5959094,"id":"Q5959094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2d73dbc594f4770ebccac741e81ac040d04535e","datavalue":{"value":{"amount":"+0.7750933170318604","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":"Q1962062$8F8A3213-F2F0-4537-81AE-E0AE99C50404","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1962062","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1962062"}}}}}