{"entities":{"Q1302159":{"pageid":1312909,"ns":120,"title":"Item:Q1302159","lastrevid":46666383,"modified":"2025-12-25T09:02:35Z","type":"item","id":"Q1302159","labels":{"en":{"language":"en","value":"Almost diameter of a house-hole-free graph in linear time via LexBFS"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1340638"}},"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":"Q1302159$97F623A5-143F-4E85-999D-DB91C5B4BF24","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"534d08246bfe3a0533b838dacdb9459e39c09f13","datavalue":{"value":{"text":"Almost diameter of a house-hole-free graph in linear time via LexBFS","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1302159$2815FCD6-1EC0-4478-BB6C-1F98A378893A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"eaf4bdc2a116be272a4d63df6018fe63375c6b01","datavalue":{"value":"0933.05143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302159$3444E314-10D6-437B-9967-F90AA5D68042","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a65af9550b8ddd0f249eda013661278556c64ada","datavalue":{"value":"10.1016/S0166-218X(99)00077-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302159$908849EE-CE31-4ECE-B0AF-9CD1B451B1C9","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":"Q1302159$858BDB88-3806-4082-AA9D-8BF213EA2AD7","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":"Q1302159$377D6DD6-F7DE-45EF-8D6F-69CCD1276F29","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bc10aa9892b9c4f398ab8507090d5710329f3440","datavalue":{"value":{"time":"+2000-03-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1302159$39D45DEF-91CD-450B-A081-385B4A3F1223","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"498f13d581fe7d664c8697e5d0e0cc1e9f184c09","datavalue":{"value":"Usual algorithms for computing the diameter of an arbitrary graph determine the whole distance matrix. Linear time algorithms are known only for some special classes of graphs, among them trees, maximal outer-planar graphs, interval graphs and distance-hereditary graphs. For some classes defined by forbidden substructures the lexicographic breadth-first search algorithm (LexBFS) computes in linear time a good approximation of the diameter. Let \\(d\\) and \\(e\\) be the diameter of a graph \\(G\\) and the eccentricity of a vertex visited lastly by LexBFS on \\(G\\). Then \\(d-2 \\leq e \\leq d\\) if \\(G\\) is HH-free, \\(d-1 \\leq e \\leq d\\) if \\(G\\) is HHD-free and \\(d = e\\) if \\(G\\) is HHD-free and AT-free. Thereby H, H, D and AT stand for house (the complement of \\(P_5\\)), hole (a chordless cycle \\(C_k\\) with \\(k \\geq 5\\)), domino (the bipartite graph obtained from \\(C_6\\) by adding one chord) and asteroidal triple (an independent set of three vertices such that any two of them are connected by a path avoiding the neighbourhood of the third).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302159$860A5E33-F78B-4777-8483-13E90F4C1349","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302159$CA336386-4935-443E-AFA5-7B54F6471014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302159$81F05E7B-3442-4775-8521-D2064196AABA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cfeec06a604f304b8ad1d50c1dce436318bf1045","datavalue":{"value":"1340638","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302159$9F730932-BA46-4D8B-A5D4-36E6290CFE12","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09fcea0fc255f4b1aa578dc9a66452879fc729e5","datavalue":{"value":"house-hole-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302159$916D13B9-9FD7-4433-9D65-82559F630AF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8182c3f6732fe433522a50e8ab625372f20faab9","datavalue":{"value":"house-hole-domino-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302159$7F29DEE7-89C7-4F16-998E-BCF0CBC63ED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a309ffd8e3e09c517781621af9e385735f4421d8","datavalue":{"value":"asteroidal triple-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302159$C855F819-46F3-4972-B985-56CB3500F0A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c249b3f66f44faf771b8258bdccd0c2d100b322f","datavalue":{"value":"lexicographic breadth-first search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302159$59FB62EE-C523-4987-981E-FF4F53A12E98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d7a6b1e80a17b8d39f4ca4c174505c465cec55b","datavalue":{"value":"eccentricity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302159$DE2FE075-D63D-4935-8E83-BDEEE134E442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd227adb1378edbe90691dff18511cebed6b0036","datavalue":{"value":"diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302159$F22B9EEE-B819-44B6-B6B3-CA8EB59B891C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5186fd99999e6921db65766363ee98e6a615dadc","datavalue":{"value":"linear-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302159$C2E49AA8-B156-4527-A2B2-C28FD6324B3D","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":"Q1302159$5D973A48-69A5-4FB0-9ABF-BAD5D4C2598E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2b8c53861a37c3b2a9cb3d33df932f7652fce48c","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00077-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1302159$A4BF8E8A-086D-4CA9-8AFD-ECE62DD29E52","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7e648606ca74780de81810bbf03a716c69bd4a87","datavalue":{"value":"W1993222648","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302159$C7427E26-6894-404F-AB23-FA7562549845","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"befc7eec7081f19e46b5cd0f89df0d17b982c7da","datavalue":{"value":{"entity-type":"item","numeric-id":5951960,"id":"Q5951960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e974454f49be950ebad209595ec03f7ee19ad6d","datavalue":{"value":{"amount":"+0.8375028967857361","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":"Q1302159$AE19C290-FF88-4EDD-899E-5651689996EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bff34c3389b2fd0a493860cf8b5316df07bef2c","datavalue":{"value":{"entity-type":"item","numeric-id":4232788,"id":"Q4232788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c403da8c897f215066e88e1c813a2ad2849253f7","datavalue":{"value":{"amount":"+0.8314639925956726","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":"Q1302159$8C7619D3-E9A6-44D1-9858-B9D25988EA21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0c6a0e8fd2a8a99354bbe11b37fd080eea6bcb8","datavalue":{"value":{"entity-type":"item","numeric-id":3044328,"id":"Q3044328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c616ebc99986913a12d9611ba733c386b13fcfbe","datavalue":{"value":{"amount":"+0.7791599035263062","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":"Q1302159$AA8B7590-3F47-41A5-9E1B-6939BAFA10C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb89ef0c48a2fadf9e991fa5910ae8106911c78a","datavalue":{"value":{"entity-type":"item","numeric-id":4446912,"id":"Q4446912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e29562dd32eddfbefe58fc291d4ca36a7fc31392","datavalue":{"value":{"amount":"+0.7692023515701294","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":"Q1302159$98A3AF07-4C51-463D-99B5-51B277F09FA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cc838552deb86b7f5968a7fb3c21623c2eec5cb","datavalue":{"value":{"entity-type":"item","numeric-id":2827756,"id":"Q2827756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f71ce82ccb15b8c1b3876c8ad61908f7e49c731d","datavalue":{"value":{"amount":"+0.7637507319450378","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":"Q1302159$0CC20B22-C44F-4B96-A3A5-427EEF1E0D95","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1302159","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1302159"}}}}}