{"entities":{"Q1186786":{"pageid":1197535,"ns":120,"title":"Item:Q1186786","lastrevid":69848118,"modified":"2026-04-13T10:45:00Z","type":"item","id":"Q1186786","labels":{"en":{"language":"en","value":"A linear-time algorithm for finding an ambitus"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 37161"}},"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":"Q1186786$2B478911-97E1-4235-A356-C9C4D39B7EF8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a38f75783c266431467271b19a4681eb2579677d","datavalue":{"value":{"text":"A linear-time algorithm for finding an ambitus","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1186786$7EA544F2-7290-4936-BFE6-620DFA9F9712","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fbffe9daeb5019217d9c5b5a75b71b3b057cdf34","datavalue":{"value":"0768.05087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186786$18BB40C0-96A8-43D9-BC37-E630729D6AB1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a2fc7c4c39373bc617d2daff251789b7e384bd32","datavalue":{"value":"10.1007/BF01758776","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186786$CCF1DEAD-04C3-40CB-BD8E-887661CD3432","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5b17683dd2eedd3f1d821a1087aa218b2b31d17","datavalue":{"value":{"entity-type":"item","numeric-id":1160451,"id":"Q1160451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186786$8BE79F9E-F6FB-49AF-840D-550CB56E8B2E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186786$0D5C1C63-7611-4319-875A-D0D0607BBE06","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1186786$C8F34A74-D639-44C5-8A68-79BD59F4A199","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ce5ffb2d93c8ca88589347eb5c01e2f6d57bbd9c","datavalue":{"value":"The paper presents a linear algorithm for finding an ambitus in a 2- connected graph \\(G\\). Let \\(s\\), \\(t\\) be two distinct vertices of \\(G\\) and \\(P\\), \\(Q\\) two internally disjoint \\(s-t\\) paths in \\(G\\). These two paths form an ambitus in \\(G\\) if components of \\(G-(P\\cup Q)\\) called bridges and divided into groups \\(B^ P\\), \\(B^ Q\\), \\(B^{PQ}\\) satisfy the property that a bridge in one group does not interlace with any bridge in the other group. That means an ambitus is a cycle cutting the graph into disjoint pieces which can be investigated separately. Fast finding an ambitus makes it possible to employ the divide-and-conquer paradigm in designing some graph algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186786$1D9C0B27-70F4-4F16-AD46-634F0CE0924F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186786$DB07174B-6111-4928-B640-FA7BC38CB2CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186786$F2A2D803-F383-4193-AB0A-561AD332B7E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186786$3143EACF-C206-405D-9FF6-1085C69C32A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186786$234EA169-3612-4A06-893A-B09A7DCC9E54","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ace131eefeb128e8e1ae8de6550a3c63937c2fea","datavalue":{"value":"37161","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186786$981DAA97-F0AC-4C96-9E39-778F157F218C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6674c31cb2e1b922c8dd1c134213920f702076d0","datavalue":{"value":"ambitus","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186786$FF188FED-7FFF-4E45-92F8-C2FE563F8BC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e865dcf04feef79efcf163ac054d2ac37b7305b","datavalue":{"value":"paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186786$A6C6C3C3-CF09-4E6C-BAC2-F834094FC024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f9fd6921fb75dc82a0e4e56b104f35b0cf8770b","datavalue":{"value":"bridges","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186786$EC0914A3-72EC-419B-A831-C3D1B7E6BC9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6cc52b35d03b83d5162d854c61cf5b039329e","datavalue":{"value":"cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186786$80B825B3-38DC-47C7-B882-7EB8EACC1928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186786$9ECFA9FA-AE88-440C-9686-869355C7B1BE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"15fb7789dd0d1691819f44cebdb975938d5b89dc","datavalue":{"value":{"entity-type":"item","numeric-id":967347,"id":"Q967347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186786$EF39A35C-2738-4381-A9A7-0C39E5935B50","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":"Q1186786$FA8146D7-C5FB-450B-B209-CF89D70C95D7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"494a6facb247170cb800c151325e05bc32fbf4ff","datavalue":{"value":{"entity-type":"item","numeric-id":3825103,"id":"Q3825103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186786$89BDB3D4-491C-4218-B9EE-C687B0EC2325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e93fcc5f5e8911813f16fcd1e3e08e519d9e013","datavalue":{"value":{"entity-type":"item","numeric-id":4767335,"id":"Q4767335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186786$20EE5A18-0E3A-4A13-960C-BDC8356C0BD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186786$6372EDCF-8873-44B6-8264-C173492E926C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc5a4256c30d82b5fb9d7745113fba963602331c","datavalue":{"value":{"entity-type":"item","numeric-id":4732130,"id":"Q4732130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186786$DE069C4D-A37A-4836-A2D0-C9714FC38EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46922753362575a6fb809bcfc673ff1c32b6470e","datavalue":{"value":{"entity-type":"item","numeric-id":5528475,"id":"Q5528475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186786$60941EAD-5C22-4FD1-B781-536FC6C6DBFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c68614ff6d1dcc1cdf852fefb79206edca8918c9","datavalue":{"value":{"entity-type":"item","numeric-id":5650693,"id":"Q5650693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186786$2F8A9BF2-06A7-4389-9249-CA43A59115A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186786$9EA7B85D-00AC-4D7C-A08D-553C8CB238DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab905d27922a85af616443e1769a1850cb9248b6","datavalue":{"value":{"entity-type":"item","numeric-id":5524326,"id":"Q5524326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186786$1CA04600-0283-43DC-8976-7668A267EF4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eefb9569597405d95da8f4b0d4f848b71cd1e5af","datavalue":{"value":{"entity-type":"item","numeric-id":1237746,"id":"Q1237746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186786$F5845653-30F6-417A-8E8C-71012ABE365D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"399170e4e1b3d1c06783026f5bac54356ddf6ae7","datavalue":{"value":"https://doi.org/10.1007/bf01758776","type":"string"},"datatype":"url"},"type":"statement","id":"Q1186786$32C2AF1F-5888-407F-8AAC-BE0E3094A796","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"affdcc6f3a5338b74ae13954e875f3e5ada53a7c","datavalue":{"value":"W1966836445","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186786$54C95858-660C-4184-91E9-1DEF2A5068A0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7760566dfc0c2ef4fc81037dfb3b9accb8b9269","datavalue":{"value":{"entity-type":"item","numeric-id":4282752,"id":"Q4282752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f895a3de1bd7f34637e7698ab50220bb8592a806","datavalue":{"value":{"amount":"+0.84631735","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":"Q1186786$87F4A2E2-1CE4-4AE0-8AE2-BB687638131D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e171e900f8a3ea62460e247f3c94c370755e48e1","datavalue":{"value":{"entity-type":"item","numeric-id":1939683,"id":"Q1939683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d45f2ee20c82a52b3976b1fbe1f05ff36db732a2","datavalue":{"value":{"amount":"+0.845784","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":"Q1186786$EF2D1458-CA4C-49C5-A7D1-A5053AC2AF44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2c9f25564fa659429dd8435c3f876eba65e884a","datavalue":{"value":{"entity-type":"item","numeric-id":1823260,"id":"Q1823260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e71edf4a6d55e407dd100e0054da82b4f2f0357","datavalue":{"value":{"amount":"+0.84447014","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":"Q1186786$C98F0E4D-BA74-45FB-BE37-FF0AC0299B95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"286a24c8fc1d7de2b30a353897b8c4f7396d9379","datavalue":{"value":{"entity-type":"item","numeric-id":3648803,"id":"Q3648803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5048b3413ef11a86a09853b4ffd24e6d67364efb","datavalue":{"value":{"amount":"+0.841649","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":"Q1186786$C2DEADD5-B469-4621-B9F7-E1D74C4F36D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20f18fd246048fdb79e3bd6885598c0a01e33416","datavalue":{"value":{"entity-type":"item","numeric-id":1329142,"id":"Q1329142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5c748fa2b276b5dfdc41a3de5fd0b8f18ca7aab","datavalue":{"value":{"amount":"+0.84053004","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":"Q1186786$C3D434D4-A464-430F-BA26-04FE8BBDB9E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e80e4278d5692c20ce45d28d9b1204a46bc0f7a2","datavalue":{"value":{"entity-type":"item","numeric-id":1882079,"id":"Q1882079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed7ec91d6ba0aebe600a5863cfe4709e2fe29bfb","datavalue":{"value":{"amount":"+0.84012437","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":"Q1186786$B531C3AC-9CBE-4FA3-9C67-B7CD5A0C574F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d061fba5597e9369233fd3b16235400bddc513cb","datavalue":{"value":{"entity-type":"item","numeric-id":5091172,"id":"Q5091172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff61f50699f3b2a00a752d469e228388f638dbd9","datavalue":{"value":{"amount":"+0.83985233","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":"Q1186786$EFFC7DEE-22F9-4976-A44C-CB72D621A82B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f88d7a7c04442b5b41e6cd255a4083dbb6fd35f","datavalue":{"value":{"entity-type":"item","numeric-id":3988850,"id":"Q3988850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfbf52b21954a2b6b9117899b499301deaadcaf4","datavalue":{"value":{"amount":"+0.8387469","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":"Q1186786$E7FA36C6-7A52-4D84-8A67-F4E7FB447ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da113e5dc278ae8e73af1974e10185685e0f64aa","datavalue":{"value":{"entity-type":"item","numeric-id":5371958,"id":"Q5371958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c9474061e6164af6fe00169770635e3e92e4895","datavalue":{"value":{"amount":"+0.8372229","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":"Q1186786$611BAA4B-4544-47A5-9503-DFDAF6537958","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A linear-time algorithm for finding an ambitus","badges":[]}}}}}