{"entities":{"Q1962066":{"pageid":1972808,"ns":120,"title":"Item:Q1962066","lastrevid":47437351,"modified":"2026-01-01T18:17:03Z","type":"item","id":"Q1962066","labels":{"en":{"language":"en","value":"LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1395031"}},"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":"Q1962066$05027822-D7CF-46E3-BCC0-5AA70D9F8D50","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4cd9739f4bfb3359696e61d9168de6942b7e1291","datavalue":{"value":{"text":"LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1962066$57811103-3126-400D-9BD7-A3D7711A14E1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"11df483e216362b7f6137e4af5916102281fe264","datavalue":{"value":"0940.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962066$D77255F5-37C1-449B-A730-399C832C2C80","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"72b7f9b12a42f920fa442aac6740b77aa0df9c3e","datavalue":{"value":"10.1016/S0166-218X(99)00157-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962066$EB6E5BA0-3969-4264-B8B0-F4A0D47556E1","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":"Q1962066$76D14668-7B93-4CE0-B0A8-FDB2750A4124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5e8ce6f4aa1d9a57c198704c5bacc005467d56f6","datavalue":{"value":{"entity-type":"item","numeric-id":685526,"id":"Q685526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$C19AB3A5-DEBD-4422-9307-A6ECCFD3374A","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":"Q1962066$76CA08D7-7C56-4DB3-A119-28225E8DE779","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b0280911b4983a386727b2c52f0e24504b6a243f","datavalue":{"value":{"time":"+2000-07-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1962066$FBDA6239-82A5-4344-A89E-0708E1A7F904","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c09da979f815c93733f6c1cc900ab2514e14c0c3","datavalue":{"value":"A graph \\(G=(V,E)\\) is distance-hereditary if it is connected and every induced path in \\(G\\) is isometric, i.e., for every connected induced subgraph \\(H=(W,F)\\) we have \\(d_H(u,v) = d_G(u,v)\\) for all vertices \\(u,v \\in W\\). In the \\(k\\)th power \\(G^k = (V,E^k)\\) of \\(G\\) two vertices \\(u\\) and \\(v\\) are adjacent whenever \\(d_G(u,v) \\leq k\\). All even powers of distance-hereditary graphs are chordal, and all odd powers are HHD-free; see \\textit{H.-J. Bandelt, A. Henkmann}, and \\textit{F. Nicolai} [Discrete Math. 145, No. 1-3, 37-60 (1995; Zbl 0838.05045)]. The authors prove an extension of this result dealing with common dismantling schemes provided by Lexicographic Breadth-First Search (LexBFS): Every LexBFS-ordering of a distance-hereditary graph \\(G\\) is both a perfect elimination ordering of all even powers of \\(G\\) and a semi-simplicial elimination ordering of all powers of \\(G\\); see \\textit{B. Jamison} and \\textit{S. Olariu} [Adv. Appl. Math. 9, No. 3, 364-376 (1988; Zbl 0684.05020)] for semi-simplicial elimination and \\textit{F. F. Dragan, F. Nicolai}, and \\textit{A. Brandst\u00e4dt} [Int. J. Comput. Math. 69, No. 3-4, 217-242 (1998)] and \\textit{F. F. Dragan} and \\textit{F. Nicolai} [Int. J. Comput. Math. 71, No. 1, 35-56 (1999; Zbl 0934.05110)] for related results on HHD-free graphs. One forbidden subgraph characterizes the class of all distance-hereditary graphs \\(G\\) such that every LexBFS-ordering of \\(G\\) is a perfect elimination ordering of all powers of \\(G\\). Moreover, the diameter and a diametral pair of a distance-hereditary graph can be computed in linear time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962066$B1B7537A-F8D1-44FA-83AF-96458BD5ECD0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962066$F86B2A89-7399-4B9F-B756-EE5C371BDEAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962066$1D95085B-9AEC-4923-A921-E3E33570130B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962066$71911899-10A3-4A34-9FD1-5658B61B40F8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"54995a1625a173497e0b0be7e2ca9c864a302d82","datavalue":{"value":"1395031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1962066$BAC1B5D6-159B-4077-A2C8-7C4F1F0CC926","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"358b2a890150a714c444c1162c9c5b41fa67317e","datavalue":{"value":"distance-hereditary graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962066$C23399E2-438F-456F-B9B9-16BB50902C1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7516dab11d300260a928576cc84b0c50e9a3330f","datavalue":{"value":"lexicographic breadth-first-search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962066$B8A2FE93-97F1-447C-AF20-84A135074ED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27d27c6e3342a6ab1fa6c7f1de58cf6528dada9c","datavalue":{"value":"perfect elimination ordering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962066$22B94377-648D-4D8F-8EF0-ABF494CDB6C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a549bf2cab0ae98b278d7fffaac4a14df7f00bf","datavalue":{"value":"metric power","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962066$45E86AF8-8691-4E65-A1E2-E1012724324E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd227adb1378edbe90691dff18511cebed6b0036","datavalue":{"value":"diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962066$5A2FCFC2-5B7A-4805-BC3F-F34AC86BD628","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1962066$7D808359-9A04-4D6D-9D15-475477DF8908","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":"Q1962066$6D44D854-AFA1-4255-B61C-754C17FD2A8A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"04a9663ba3682d03e2c51a51cb41e256e68efebc","datavalue":{"value":{"entity-type":"item","numeric-id":1901030,"id":"Q1901030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$2D80F5AC-4122-41CC-A9CA-A235274E3BAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f12af41ed187d70b4f8551c0debc8584dce55dda","datavalue":{"value":{"entity-type":"item","numeric-id":1084114,"id":"Q1084114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$581F63BF-CCA5-45FD-82E8-FDF1F5C81B80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ed30162266de4356ebf61b1f97b84f128fe7436","datavalue":{"value":{"entity-type":"item","numeric-id":1084416,"id":"Q1084416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$186C3B3E-9D58-480C-86F2-562F328E46BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32c1a4180aeef07849b9be70ab86fcca0a7db8ca","datavalue":{"value":{"entity-type":"item","numeric-id":1815326,"id":"Q1815326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$2823BA28-D903-4C82-913A-935620190A03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a45af94487317a229d0f8edc5c798e74da851737","datavalue":{"value":{"entity-type":"item","numeric-id":1363684,"id":"Q1363684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$A08838E1-E60D-4CE5-AF63-9ADEC86B50A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c697be7d2af4a6938c4026417e7bd5fd666f7fbf","datavalue":{"value":{"entity-type":"item","numeric-id":3791188,"id":"Q3791188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$59D1DD73-7897-4DB2-A031-87A441B09908","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9530e978c393e346bc33eebac05254320f0116b1","datavalue":{"value":{"entity-type":"item","numeric-id":5054776,"id":"Q5054776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$8292C4FB-0066-4E21-9CC6-6226ECB182C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3edef11026e17dc8f256d301ddca86147ccafa2","datavalue":{"value":{"entity-type":"item","numeric-id":4255812,"id":"Q4255812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$FC1F7964-AEAE-4C4F-863E-20C5E01EEAE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a45938c6aeaa81838370e86e9c3b77537d0a5238","datavalue":{"value":{"entity-type":"item","numeric-id":4272121,"id":"Q4272121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$844CB032-7ED3-4D61-8D6B-E2080A5636CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebd0293f4bb61e0400a6439bf5b2433073065c05","datavalue":{"value":{"entity-type":"item","numeric-id":3222876,"id":"Q3222876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$C4B88909-AC4D-496A-9BCE-89A3C8B92332","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":"Q1962066$3A4CC09D-D659-42FF-A95F-3965D8DF5EF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d609e41497c03f50ec67ae006228d6ca122b2752","datavalue":{"value":{"entity-type":"item","numeric-id":908944,"id":"Q908944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$F3C2CC99-5E24-4496-94FE-AAC937A53096","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba53c03305fcd0c780c8b0cf1f62c0b6d41fecfa","datavalue":{"value":{"entity-type":"item","numeric-id":4154586,"id":"Q4154586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$B74D9425-FAF6-4FE8-AACC-A9710E7E373B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79981124712be007c2eddc8be25e8e3e4dfef1f5","datavalue":{"value":{"entity-type":"item","numeric-id":1825204,"id":"Q1825204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$748E7E3C-B29B-43E2-805C-DFD396797896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3b7b50f9c72a9a4464e36661c17354b7aa01a35","datavalue":{"value":{"entity-type":"item","numeric-id":1175796,"id":"Q1175796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1962066$562E0D39-D7DE-4026-A9A5-DEE039005EAE","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":"Q1962066$20789077-A3BF-43D0-BDDE-66CC8ACF12E1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1da105503894552f15c057421d4ba0d52a5ef954","datavalue":{"value":{"entity-type":"item","numeric-id":1363684,"id":"Q1363684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1af3e85eac160920b0478fecfc087ffba825777c","datavalue":{"value":{"amount":"+0.8017425537109375","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":"Q1962066$D0F3A05C-D9B4-429E-92DA-BFAF16E46F75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f0e01d5442d57a99a64cf627f2ef9c8a4629dc1","datavalue":{"value":{"entity-type":"item","numeric-id":4210215,"id":"Q4210215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92884033f443494387cc90fac8748e7b5469d385","datavalue":{"value":{"amount":"+0.801742434501648","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":"Q1962066$296D2117-DBE7-47C6-AB83-6B8AA3C94526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90e692f8ae96c6b28900911298c4a40ba4925205","datavalue":{"value":{"entity-type":"item","numeric-id":1901030,"id":"Q1901030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a69a0d651ba4ed8ae4e325256dd90103b9482fff","datavalue":{"value":{"amount":"+0.7763253450393677","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":"Q1962066$3A55A309-DCBA-4ABE-B847-CDD1AAB9839F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49852327a29a30b2f7656fe5f7be1fb0d186a452","datavalue":{"value":{"entity-type":"item","numeric-id":4254590,"id":"Q4254590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd39c35666652df7d40ff4446f6d86223de73103","datavalue":{"value":{"amount":"+0.7630124092102051","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":"Q1962066$F33F71F4-4452-4405-AE41-F4A0FF890406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa60de1c172605da053cb1a97965439317c07323","datavalue":{"value":{"entity-type":"item","numeric-id":1302159,"id":"Q1302159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"892536b686d30aa65f6f32178c4788bc8a1c5139","datavalue":{"value":{"amount":"+0.7512133121490479","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":"Q1962066$56D3D41F-7D47-4435-ACB7-009EBD8E2906","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1962066","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1962066"}}}}}