{"entities":{"Q5957357":{"pageid":8134159,"ns":120,"title":"Item:Q5957357","lastrevid":41821999,"modified":"2025-05-08T17:58:32Z","type":"item","id":"Q5957357","labels":{"en":{"language":"en","value":"Recognizing pseudo-median graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1716749"}},"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":"Q5957357$6BC64555-B13E-4B04-935E-1016F1F35375","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ba6ad3497c8803aadc0994b08b56dda6d018664b","datavalue":{"value":{"text":"Recognizing pseudo-median graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5957357$6E5E859B-BFD5-41D8-835F-E5977F7D3B28","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b80a61b632804d09c4619647015f77c46de2e251","datavalue":{"value":"0990.05112","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5957357$FFBFE24C-FB8C-4AAC-BAFE-09ECE233B420","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8986f4d77561e62ad398acac48e82011e9d2d433","datavalue":{"value":"10.1016/S0166-218X(00)00327-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5957357$4D196677-55FF-4BC1-8907-612C62343BEC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"77729d3ae775c05f25f3e0bb9277ed7177016618","datavalue":{"value":{"entity-type":"item","numeric-id":233536,"id":"Q233536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5957357$B48710C7-B21D-432A-8A6F-C040500AC667","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":"Q5957357$7D9F6399-8B8F-45E1-B2DE-A54786216B11","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"19b82f60c4bae3f7fc50cdd7754a79a80256f28d","datavalue":{"value":{"time":"+2002-08-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":"Q5957357$10A8879B-7FE3-4B96-AB6C-DC13F1A081F9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7270e4302e9a9abc87d320b2549172ea7bbb849a","datavalue":{"value":"A median of a triple of vertices \\(u, v, w\\) of a graph is a vertex \\(x\\) such that \\(x\\) lies simultaneously on shortest paths joining \\(u\\) and \\(v\\), \\(v\\) and \\(w\\), and \\(w\\) and \\(u\\), respectively. A pseudo-median of \\(u, v, w\\) is a triple of mutually adjacent vertices \\(x,y,z\\) such that \\(x,y \\in I(u,v)\\), \\(x,z \\in I(u,w)\\) and \\(y,z \\in I(v,w)\\) where \\(I(a,b)\\) consists of all vertices on shortest paths joining \\(a\\) and \\(b\\). A connected graph \\(G\\) is a median graph if every triple of vertices admits a unique median. \\(G\\) is a pseudo-median graph if every triple of vertices admits either a unique median or a unique pseudo-median. The author characterizes pseudo-median graphs and gives a recognition algorithm for these graphs in \\(O(mn)\\) time. Both characterization and recognition partly make use of results from a paper of \\textit{H.-J. Bandelt} and \\textit{H. M. Mulder} [Pseudo-median graphs: Decomposition via amalgamation and Carterian multiplication, Discrete Math. 94, No. 3, 161-180 (1991; Zbl 0743.05055)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q5957357$1C4E4D46-6907-433A-B212-F5D0A23ED55A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c4d08f81dccf0def423a8aaa09abdd52c85c61ef","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5957357$EEAF1555-5FFF-46EB-A433-FFC0C3A875C2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5957357$1B419D54-2E24-4A4A-8B60-8F79896025C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5957357$12B5CA5E-FB32-4962-99BE-E4A48CAFA695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5957357$A47942A6-9F3E-456F-84A6-143B2FA9143D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"11a19f55eeaedf20a7947b07fddeeae2dfcb1758","datavalue":{"value":"1716749","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5957357$A68FAD40-AB5F-4E4F-BFA2-A06E7BAEEBB4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c6de49d360a2b5fe21d22b54ae7d728070049858","datavalue":{"value":"median graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5957357$CB23F618-F26D-4CA1-964E-B6A6F09272F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"827c1832c345c44d874c54292c608ee0bf53265b","datavalue":{"value":"pseudo-median graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5957357$D16C2256-62BA-45BE-AB51-D22891FF740D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5957357$EC86B351-A701-4E87-9B81-B235F3A877A1","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":"Q5957357$490B0F46-44C7-498B-BF36-B5A500006D3E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f6845f81e38582f9f9addef8894205413abd86a","datavalue":{"value":{"entity-type":"item","numeric-id":3279320,"id":"Q3279320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5957357$361A036D-D4AD-4A61-B348-DF1D195B4F7C","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":"Q5957357$0277BA19-F169-4C4C-AFA9-3DB211798406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efd3d82c78221bc3147ad309875c05db977b805e","datavalue":{"value":{"entity-type":"item","numeric-id":1182965,"id":"Q1182965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5957357$3159EE4B-F691-4EAD-AEBC-6C49CA49325F","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":"Q5957357$472A93A9-6EE5-406D-9B51-EEC905444430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b28854ad3f556fda04e9573181c7d11194fc4bcd","datavalue":{"value":{"entity-type":"item","numeric-id":4847142,"id":"Q4847142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5957357$0700203C-7300-4357-9EF5-6C2FADC045CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d83ded69ecce9af3aa534d2a2e450d1ed01ba81e","datavalue":{"value":{"entity-type":"item","numeric-id":1285576,"id":"Q1285576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5957357$043D9053-45E9-4FC7-8EC3-73F425FDB771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97bd0bb0da0bbc97dbb09091ca625479e6a9a44a","datavalue":{"value":{"entity-type":"item","numeric-id":4523707,"id":"Q4523707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5957357$3766B237-55DE-4C24-9BAB-D74A012665E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3a6c7d62e6d18a5c3506f6fedc088624d640514","datavalue":{"value":{"entity-type":"item","numeric-id":4032985,"id":"Q4032985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5957357$3E4392F9-9B43-43C8-8CAB-F4BA7970C4E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77d79b24dce7adb02556ef7d10eca541893551f3","datavalue":{"value":{"entity-type":"item","numeric-id":4264556,"id":"Q4264556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5957357$829D7980-D2F2-48C0-BBB6-B687A379F5C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48cefa05d704d074dd504e3354a9ead2b249764a","datavalue":{"value":{"entity-type":"item","numeric-id":3890733,"id":"Q3890733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5957357$FCD3F34C-0D2A-4607-8117-EB0A26CA413F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adc08b658fe9212f28a5ba008ca7499829fdebc1","datavalue":{"value":{"entity-type":"item","numeric-id":5618400,"id":"Q5618400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5957357$2845A3BD-0813-45B7-9372-C01A5DD29ECB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"773abe2709797ad888e3ddd08a8cf4097dc23542","datavalue":{"value":{"entity-type":"item","numeric-id":3824339,"id":"Q3824339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"490297c7d9a3153fcb21a8d7202c6c1d60e2dc32","datavalue":{"value":{"amount":"+0.8924959","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":"Q5957357$7C4BD603-6B11-4F88-B672-B632659C181E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8c4aa1fcf1b12734be31ac55ec42eb64e62b129","datavalue":{"value":{"entity-type":"item","numeric-id":1285576,"id":"Q1285576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2620b0a6ebcfbe449946373dcddfb372c444ccc","datavalue":{"value":{"amount":"+0.8604611","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":"Q5957357$523962C0-D289-4640-9948-9930AEA25B17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86531dc33b7c7a4a830c4daaf3bdfd34bdf16cc6","datavalue":{"value":{"entity-type":"item","numeric-id":872051,"id":"Q872051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bf926b9936c2be827c0714ff33f4cee21c005bf","datavalue":{"value":{"amount":"+0.8573736","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":"Q5957357$E97716CA-088E-4EFD-B59B-DAD78FDFD547","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab67a9cf2a2f6b14f31a574cf400b8d4a039dd0e","datavalue":{"value":{"entity-type":"item","numeric-id":864135,"id":"Q864135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab2639421688abf8d0d462dccb88069259abdfa5","datavalue":{"value":{"amount":"+0.8517597","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":"Q5957357$FBAEE448-5117-410E-A4A9-3F310F883350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"698dc6c4128c47b759acdc582d062a34c3cecc32","datavalue":{"value":{"entity-type":"item","numeric-id":762504,"id":"Q762504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70b5c841f4efc5d59058e3b870ccf886a91ec137","datavalue":{"value":{"amount":"+0.8492129","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":"Q5957357$EFE0AC70-E5AE-452A-84BF-4757B2078F6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da2684498436badeaae6aa66bc66f0850e48b68c","datavalue":{"value":{"entity-type":"item","numeric-id":4857430,"id":"Q4857430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75df3d5db6047e6e02f10bc8fb4e1ae60f2f3d16","datavalue":{"value":{"amount":"+0.8461095","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":"Q5957357$10462FDA-60C2-448E-A593-40503C7E2A58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5137707c908952291750748b9361dc634289d0f","datavalue":{"value":{"entity-type":"item","numeric-id":1331889,"id":"Q1331889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3372208865c496d4d4de1d9b59b524902bb35445","datavalue":{"value":{"amount":"+0.83633673","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":"Q5957357$DC373D89-AD86-411E-B781-6954256DA44C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"edd92fcf9f1686301420e095e3d158e1c6f62221","datavalue":{"value":{"entity-type":"item","numeric-id":1182965,"id":"Q1182965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb5ab77f5ee77468c6321df2fb066daf4885aead","datavalue":{"value":{"amount":"+0.8361079","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":"Q5957357$B1223B57-66E9-460F-A97D-BD20054C88AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c5f620e048fba55d7d56e9c0612a327476aadf2","datavalue":{"value":{"entity-type":"item","numeric-id":2784516,"id":"Q2784516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a01f8de8fb1fec0fa68bc3983748d40964a80c90","datavalue":{"value":{"amount":"+0.8357115","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":"Q5957357$BD0757B3-684E-4C9E-BFFC-2EEADF90B9ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"233ded90a3afed78201beb6ac27eecf3736fe845","datavalue":{"value":{"entity-type":"item","numeric-id":3748084,"id":"Q3748084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35c382bbf4397f7656f612c40dc93c065085904e","datavalue":{"value":{"amount":"+0.8341744","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":"Q5957357$F4AC1B06-62BA-4AA2-A1C7-1989BCECD567","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5957357","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5957357"}}}}}