{"entities":{"Q4511223":{"pageid":6540816,"ns":120,"title":"Item:Q4511223","lastrevid":108652085,"modified":"2026-11-09T15:31:27Z","type":"item","id":"Q4511223","labels":{"en":{"language":"en","value":"LexBFS-ordering in asteroidal triple-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1522927"}},"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":"Q4511223$FC66BB61-9CA8-4696-9994-3A64D86304EC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"51b095c07c7ba32ee7349938901e78318dded44a","datavalue":{"value":"0966.05074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511223$77EA2530-F2EE-484B-829D-BBA8563EB491","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1f6dde031be265f6ad0a54e71ef2fbc43ca12de0","datavalue":{"value":{"entity-type":"item","numeric-id":269717,"id":"Q269717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4511223$38397CA0-2FAE-4D43-A125-E35053A79638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c82e19a032ca9256003aa2cc5ca5843bbf680284","datavalue":{"value":{"entity-type":"item","numeric-id":293189,"id":"Q293189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4511223$85F41BA7-DED0-42C5-919A-9C5AB7B784A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a404e628e9f9679ad57cedf78ce6f43b328845f1","datavalue":{"value":{"entity-type":"item","numeric-id":217890,"id":"Q217890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4511223$4C518E25-1D60-4C1E-AE66-FB6111910694","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7b19c0f454ec23580c4f40f0efbf241531effadc","datavalue":{"value":{"time":"+2001-08-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4511223$0DEC03FC-A3B5-4A0E-9C6C-361C8426417F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511223$D90624D3-4027-4F94-A7B0-A425619EC049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511223$BB54416A-1230-4870-8B0F-120B11531CE6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"76435ac34cc9cb073d49ea5d982fe0d0235af08f","datavalue":{"value":"1522927","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511223$6B2B6547-B891-41BC-B8C3-3FCE9EE76628","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6af21da96a32ee0b528820d93691db7ad524be9b","datavalue":{"value":"LexBFS-ordering","type":"string"},"datatype":"string"},"type":"statement","id":"Q4511223$A723A80C-BF98-4998-B818-334AFD95C65F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa7ab4fd389eb124a320e77dbb93bd6b5d183aa7","datavalue":{"value":"AT-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4511223$7BC9B385-FF37-4DB4-A236-35B17B1A0199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"972b47051b12a25f42ccd0a9702464009e0dcd44","datavalue":{"value":"permutation graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q4511223$EF9BBB65-0ECE-4654-8278-0EC978406262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5139f7b3ac3b7fb243adf74e3bd928a38ff6bb71","datavalue":{"value":"Lexicographic Breadth-First Search","type":"string"},"datatype":"string"},"type":"statement","id":"Q4511223$28DD344F-02B8-4794-B464-64845A43B1A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"722c934d4cb69517a66dd706aade10e74fbfd3bd","datavalue":{"value":"linear time recognition algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q4511223$7D04D67C-014B-4AD8-BF32-28FD5B3DB7A3","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":"Q4511223$E5CE0047-1341-474A-937F-537645E0D850","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c97d8078d541cf497614a611e1a8f9aab4efa19","datavalue":{"value":{"entity-type":"item","numeric-id":1627146,"id":"Q1627146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5909e49b0f714851a1f1a01d590199e1ba90cdef","datavalue":{"value":{"amount":"+0.8368483185768127","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":"Q4511223$F874D100-FA06-4198-8853-F5A40FC2B1C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"623aa35733c4b9576e8eb37d48919302fe679764","datavalue":{"value":{"entity-type":"item","numeric-id":528559,"id":"Q528559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"912e85a905bdecba8d52ec53f6d306c91e30cf06","datavalue":{"value":{"amount":"+0.7827918529510498","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":"Q4511223$F10EDED1-F44D-40D0-9998-9C8B86F30552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19a665214bb8147f93cc2df895c6e1edabfb47bb","datavalue":{"value":{"entity-type":"item","numeric-id":5470820,"id":"Q5470820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f000a7e0501efd0477e76d59adf757b4ed86f5f","datavalue":{"value":{"amount":"+0.7652718424797058","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":"Q4511223$DE558DA6-8C29-4A7E-B23A-C02F01CF5598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5636b5b04d6fa8e5cef3f390aa88afd4fa07664","datavalue":{"value":{"entity-type":"item","numeric-id":4250178,"id":"Q4250178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"645bbd03663b8f92ed8f0190cced80de0bfda352","datavalue":{"value":{"amount":"+0.7558581829071045","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":"Q4511223$7493628D-FBC3-4E4B-9346-C871F52254A5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1695e820385c5596bd724c7a0aaf18d5e4c33ab9","datavalue":{"value":{"text":"LexBFS-ordering in asteroidal triple-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4511223$06D98409-0562-4F36-BCB4-A622520A3D42","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"11a1656104512efb682b2c83e823bce597f774dc","datavalue":{"value":"10.1007/3-540-46632-0_17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4511223$C02B5F05-D76C-42EA-A520-317C011B1225","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a831ce4da56ae4197b2bdaaf5a9242382e69cac8","datavalue":{"value":"The authors derive from a result of \\textit{D. G. Corneil, S. Olariu} and \\textit{L. Stewart} [Linear time algorithms for dominating pairs in asteroidal triple-free graphs, SIAM J. Comput. 28, No.~4, 1284-1297 (1999; Zbl 0926.68094)] that the vertex ordering \\(<\\) of an AT-free graph \\(G\\) obtained by applying the Lexicographic Breadth-First Search (LexBFS) twice to \\(G\\), where the second LexBFS procedure starts in the last vertex of the first LexBFS, has the following metric property: If \\(u < v < w\\) and \\(d(u,w) \\leq 2\\) then \\(d(u,v) = 1\\) or \\(d(v,w) \\leq 2\\). The authors modify this ordering to provide a new and simple linear time recognition algorithm for AT-free bipartite graphs (i.e. bipartite permutation graphs). The first linear time recognition algorithm for AT-free bipartite graphs was found by \\textit{J. Spinrad, A. Brandst\u00e4dt} and \\textit{L. Stewart} [Bipartite permutation graphs, Discrete Appl. Math. 18, 279-292 (1987; Zbl 0628.05055)]. For the entire collection see [Zbl 0933.00045].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4511223$322BA538-064B-4A72-BB4D-4C508DB42D5B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4511223$4502892A-C385-485F-BF2B-4AC90DB316E9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"LexBFS-ordering in asteroidal triple-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/LexBFS-ordering_in_asteroidal_triple-free_graphs"}}}}}