{"entities":{"Q1902306":{"pageid":1913048,"ns":120,"title":"Item:Q1902306","lastrevid":43410197,"modified":"2025-07-25T13:59:22Z","type":"item","id":"Q1902306","labels":{"en":{"language":"en","value":"Finding a maximum matching in a permutation graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 818364"}},"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":"Q1902306$4349C233-9900-452D-B5C1-FE2EFBA623B7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"81cef13ddc8731948104a248746b6a74515a1f59","datavalue":{"value":{"text":"Finding a maximum matching in a permutation graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1902306$A81F05D5-5730-4400-8865-C3A5335841FB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c39e3ae53c7a8387c5d41b2bfa25c113b63b64b2","datavalue":{"value":"0831.68076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1902306$88BD0E0F-6FAA-41C3-B1AF-D6891D7597DC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1e40740f9b8556c225329ada32f23c4c9deed5cd","datavalue":{"value":"10.1007/BF01178659","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1902306$3BA74ED6-305D-4B7C-8196-499E991F7688","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba81531d441e099b67c5a341d26c2b25e00d7f91","datavalue":{"value":{"entity-type":"item","numeric-id":1209982,"id":"Q1209982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902306$D8A09079-06B0-4828-A2F1-E420C24723DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c95b35470c02ab57f60a761264c493d92c52a5a2","datavalue":{"value":{"entity-type":"item","numeric-id":1209983,"id":"Q1209983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902306$8D2CC600-8DD5-46AD-B798-E6689746B765","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902306$49BFB920-E22E-4D6D-9C7A-C7AC4973D0C3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"622c2f71ed8d7028e10f4c9b72f54a2f381d5eab","datavalue":{"value":{"time":"+1995-11-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1902306$C8C7EBB7-A6E1-4CE3-BDD7-266C7E34CE57","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a7a112e880724fd352acdec6adc0705e3b3fb261","datavalue":{"value":"We present an \\({\\mathcal O} (n \\log \\log n)\\) time algorithm for finding a maximum matching in a permutation graph with \\(n\\) vertices, assuming that the input graph is represented by a permutation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1902306$07D3EFA4-01E3-497C-8016-4393554F408C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1902306$E4392032-106E-4764-AA34-2745DE77420D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"df5872a0a47343972cc8e5d11d09280815cb2542","datavalue":{"value":"818364","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1902306$82BD785F-E1FC-48A4-BC39-15D74F63E9F7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3842779000597abe3dc3cef2451250276bc01d5","datavalue":{"value":"maximum matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1902306$98CB9BBF-8C05-473A-B83C-2EFED8724F01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cba4f4e6b1d6add40394622cbe47bbb0afecf1c","datavalue":{"value":"permutation graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1902306$B13AD301-BE23-49E7-9103-EE187884D47F","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":"Q1902306$04ECA073-4541-4A7F-81FB-04393375660F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f61c5d68d33f8ea7723f3ac70afbbc88052e3402","datavalue":{"value":{"entity-type":"item","numeric-id":3258697,"id":"Q3258697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902306$3002D83B-7DC9-41EC-9437-3BD0FEABD8DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902306$010C4278-8366-4D04-A0C0-5EC164A209DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ba2a12b9e1e5e9bec0aede63e4f328974ff5dc6","datavalue":{"value":{"entity-type":"item","numeric-id":1241058,"id":"Q1241058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902306$D3F413DA-16A3-4EC5-8F1D-DFA266C546F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902306$8771D16F-1BF0-4C0B-8FFB-965C730379D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dd69a1563f490441e0bb585dab5fd4b25fe22b9","datavalue":{"value":{"entity-type":"item","numeric-id":1209984,"id":"Q1209984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902306$C0DF1E9F-C88B-4389-826F-F9B5E556BFC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cd900a9928338cdadd8e18c47b33b430f9560c7","datavalue":{"value":{"entity-type":"item","numeric-id":5602691,"id":"Q5602691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902306$49CA9CBE-295E-4BC5-9ECA-C357B6368489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"565e1c631f28f5626e28b4b72f070c887ee0b094","datavalue":{"value":{"entity-type":"item","numeric-id":3685215,"id":"Q3685215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902306$039B8CE8-9EA5-47F0-81E4-AB86F3340A79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a93f862fd209cba09f4612af821b01e8d18996a9","datavalue":{"value":{"entity-type":"item","numeric-id":685476,"id":"Q685476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1902306$92011F11-B6E0-4765-A3E0-49C793124F2B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b6f10f9d83a8d5021426e0d9f93081e9bf8663b8","datavalue":{"value":"https://doi.org/10.1007/bf01178659","type":"string"},"datatype":"url"},"type":"statement","id":"Q1902306$2F8B1229-4371-4BD0-A212-61A300B6D415","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"23ad0e37c85877a84f3f0d7652580ac1d3a48196","datavalue":{"value":"W1969693641","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1902306$3CB4C2AC-C4BB-438F-8F21-9B45D7A1109F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86864b906ab59d90a8a870253b2eef100fda32c9","datavalue":{"value":{"entity-type":"item","numeric-id":916397,"id":"Q916397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdab26347d89da3ed210a6dfb2ee29d7f966ff64","datavalue":{"value":{"amount":"+0.9102069","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":"Q1902306$0EBD82FB-6F57-403D-92ED-1894FFE16903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d28a131fd3d29dae9994537bc13e0cfe291dd5a","datavalue":{"value":{"entity-type":"item","numeric-id":1709508,"id":"Q1709508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a538dbe0f24b1e0fbbe0d5142c04a52e84d7c01","datavalue":{"value":{"amount":"+0.90010166","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":"Q1902306$2A257753-7E29-45F5-A342-207BB5B64379","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"357e7c23f9a65ecd50fdf9e31335df2a2bdec533","datavalue":{"value":{"entity-type":"item","numeric-id":1324433,"id":"Q1324433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8e3301e7b7eef4de6d6cd035ddb3e3df3c2cc2d","datavalue":{"value":{"amount":"+0.8935277","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":"Q1902306$14A1EAB5-5630-45A4-BA85-571D9108B1EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"481b6814a9ee4267da530e36153596b457aad031","datavalue":{"value":{"entity-type":"item","numeric-id":1010667,"id":"Q1010667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fb24e2e2d98805084d8f18f9f4bc76e2235cff0","datavalue":{"value":{"amount":"+0.8930575","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":"Q1902306$E985E79D-C81D-41D0-A1EC-5F8A8A9B05E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa8182a41af685c562a4a2a8071dd568740bc5fc","datavalue":{"value":{"entity-type":"item","numeric-id":3745302,"id":"Q3745302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac3950efbd0d51da7b7810f0bdde677bd7fe0f2e","datavalue":{"value":{"amount":"+0.89147586","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":"Q1902306$9D8F4BC8-444A-4D84-A97B-E1F674FB9059","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79e7d65550f206c4e68c5ad76dd73fac4e10aff4","datavalue":{"value":{"entity-type":"item","numeric-id":1209984,"id":"Q1209984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"142f7745276631359c26001175befb6f732a6a4f","datavalue":{"value":{"amount":"+0.89071745","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":"Q1902306$F1BE65F7-6765-44EF-8A74-F62C1A0D9AD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70a7c775452bc97158e6f4136a1085152ea06225","datavalue":{"value":{"entity-type":"item","numeric-id":1363677,"id":"Q1363677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5592215cbf82e08459e9095563053652bcf64c0d","datavalue":{"value":{"amount":"+0.8875158","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":"Q1902306$3D8CB5EF-FCBC-4709-857A-BFAC703D7093","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e65e54ceffe500e00ba4d80ab495005fc15001a","datavalue":{"value":{"entity-type":"item","numeric-id":1949755,"id":"Q1949755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb89b11ebc20826dfac1ea96589f1abdc956ceeb","datavalue":{"value":{"amount":"+0.8866327","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":"Q1902306$3AFA1EB5-DC52-4602-90D8-500F88D32E9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5713f7a8a6fae5c38d1e466305ab98d478618702","datavalue":{"value":{"entity-type":"item","numeric-id":418005,"id":"Q418005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"009da4055ef54d73f2db33ce9c0c5a093191f4bd","datavalue":{"value":{"amount":"+0.88393396","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":"Q1902306$D5820F03-76E0-4DA9-AAB1-F45C729FCE9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b4cc1e79cfb1f8999aed5e3509513706dab69b7","datavalue":{"value":{"entity-type":"item","numeric-id":3031945,"id":"Q3031945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"361ea7cb09200e72fc0af59c84c79c9c9f4fb410","datavalue":{"value":{"amount":"+0.88194823","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":"Q1902306$DAC25779-06EB-4754-A5BD-D4C82F401DE4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1902306","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1902306"}}}}}