{"entities":{"Q1814097":{"pageid":1824839,"ns":120,"title":"Item:Q1814097","lastrevid":73017591,"modified":"2026-04-14T09:25:08Z","type":"item","id":"Q1814097","labels":{"en":{"language":"en","value":"An efficient algorithm for finding a two-pair, and its applications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 10059"}},"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":"Q1814097$CE9A27B7-5683-4213-BE90-E8B96B702299","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"53e9168e6f9cbe0a1eaf74561d5bbcdeb2496712","datavalue":{"value":{"text":"An efficient algorithm for finding a two-pair, and its applications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1814097$5C831A7C-C087-4C83-A5F4-6098F8D0F9A8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4e4fc22cce1bc9fc7b69edaac151ff89eeafb77d","datavalue":{"value":"0748.05085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814097$ADE57045-E763-49C3-A14F-12A52485AA00","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b3c687b421f338107d3c7a8b38a6697ded2af5c8","datavalue":{"value":"10.1016/0166-218X(91)90033-S","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814097$57F1F015-0BB9-4425-B267-0B33AF78D805","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6176b5644d403b2413c99fd6eb40e53520884999","datavalue":{"value":{"entity-type":"item","numeric-id":686256,"id":"Q686256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1814097$102842B9-CC0F-4722-87E9-C0A2352D6CA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0e52a12d90ca5312fef7acb3a90e1100b17ed79f","datavalue":{"value":{"entity-type":"item","numeric-id":189690,"id":"Q189690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1814097$B98A4476-92F5-40D8-BD14-21A2AD75D01E","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":"Q1814097$F612369D-F7FE-46CD-9A4A-F8084E8ACBB1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1814097$DB28EA32-086B-464E-910C-29544EC38D6A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"52d58795cd67c65ee162e051426516886610f40f","datavalue":{"value":"A two-pair in an undirected graph \\(G\\) is a pair of vertices \\(u\\) and \\(v\\) such that every chordless path between \\(u\\) and \\(v\\) has length 2. This note presents an efficient \\(O(| V|| E|)\\) algorithm to decide if a given graph \\(G\\) has a two-pair and output one if it exists. The authors discuss applications of this algorithm and mention that this implies new and faster algorithms for the following four problems on weakly triangulated graphs: minimum clique cover, maximum clique, maximum independent set, and minimum colouring. Each of these problems can be solved in time \\(O(| V| T)\\), where \\(T\\) is the time required to find a two-pair. Previous algorithms for these problems had complexity \\(O(| V|^ 5)\\). Hence this new algorithm implies an improvement by a factor \\(| V|\\). Applications to computational geometry are also discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1814097$CBF701C4-54F0-42B7-A182-A454B6477A6A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814097$AED9C161-C765-4483-9C1E-684FEE7C011C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814097$FFBF9763-944E-48CE-BC9A-805D9C84ED29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"239a4a174af03c82b61364f762873d53ef0a37ef","datavalue":{"value":"05C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814097$F8272416-17D0-4918-81E2-2439AE1BB8DA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d2fdbedb5a94b7556c9c3b68fa6533d1b4e4b3aa","datavalue":{"value":"10059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814097$59FF7DC3-EBC7-45A1-B47F-2A68563DFC3B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f582a718272f378714c41be3f95da8bfaf560de","datavalue":{"value":"chordless path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1814097$6DFFA84F-AF13-42EF-AA54-D044358C9197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1814097$7B7E880E-82D8-4704-8259-76B43045DB7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f64edf4931c235159e5cb3d71e4f48ef06346aa","datavalue":{"value":"weakly triangulated graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1814097$0765053B-3B35-4E28-B47A-5AAA6D594DA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1814097$8DDBB3D0-8BC9-4888-89B1-BB75F72EEBD4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eee744981d92ac19b8d353f3a45a83ebd916fb73","datavalue":{"value":{"entity-type":"item","numeric-id":558237,"id":"Q558237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1814097$816A1056-16FC-49E6-A94A-0E23032B86DF","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":"Q1814097$50C990B2-32E3-40B6-A6EF-4126E4BD39E8","rank":"normal"}],"P223":[{"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":"Q1814097$8FF18355-18F2-48E4-BAFF-AAC7C321BE75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cca8dca2374646f727033f5b4cdf33c5889a9248","datavalue":{"value":{"entity-type":"item","numeric-id":3828050,"id":"Q3828050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1814097$C531E8D1-D694-43A3-B55D-7CF10A8675AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec5e921b4353c1a7c0359fb077421b5442f2ad52","datavalue":{"value":{"entity-type":"item","numeric-id":918225,"id":"Q918225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1814097$02E96827-E7CA-42F0-80B0-2D49BDD44B45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a75892efb8c423df4e08c3a2522f9c8641bb850b","datavalue":{"value":{"entity-type":"item","numeric-id":3799261,"id":"Q3799261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1814097$D6F96B36-E762-4FD6-A99B-66FD596054AD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f8c8fff64ff051c715b6b10daac23de50f63a03b","datavalue":{"value":"https://doi.org/10.1016/0166-218x(91)90033-s","type":"string"},"datatype":"url"},"type":"statement","id":"Q1814097$BA13D5F7-A1B3-4A82-8C3F-0CC6C4DC0D7B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a9ef9ce2541879eb783172c9644cca1ec53ab0fa","datavalue":{"value":"W2024353971","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1814097$F59AE6FB-7617-4F4B-B127-0165761765FF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68c77d86ee099632ca80763a63236328b4da177f","datavalue":{"value":{"entity-type":"item","numeric-id":1069866,"id":"Q1069866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f864b1548496bd23daf4e15ae3b814d79f2d436","datavalue":{"value":{"amount":"+0.877593","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":"Q1814097$9F3C38E5-0429-492D-8234-355EFF599ECE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52ae3720f088d1aff52455580c2f2c95daaf264c","datavalue":{"value":{"entity-type":"item","numeric-id":674438,"id":"Q674438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10f6229bd775f6c0c42088babf15ca421c2f11e5","datavalue":{"value":{"amount":"+0.8753169","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":"Q1814097$3507506F-1BB3-4FE2-8D1D-48B5EA117854","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3cb36786b4ef330754bdfadf5d2f63ddc7dc347","datavalue":{"value":{"entity-type":"item","numeric-id":4474103,"id":"Q4474103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e642c8a70dab95d9fdfcaf178d54da25b08bd421","datavalue":{"value":{"amount":"+0.85718274","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":"Q1814097$F47147D3-C73D-42D5-8107-E07D32D9A905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3965bd91c4de7f6edeac9348095907bbec18f788","datavalue":{"value":{"entity-type":"item","numeric-id":3026754,"id":"Q3026754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54606ee5c4583eba415806bd84d9d20e565a5f6f","datavalue":{"value":{"amount":"+0.8524302","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":"Q1814097$FB0C3887-C43B-4BB5-AF4E-11CA6C408BC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"adb3cfcbe72b9b8fd19397bfe9ccebc53c31eeb4","datavalue":{"value":{"entity-type":"item","numeric-id":300238,"id":"Q300238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad7d0a94192cb4f4af1c56fe52e181dfaa412dc0","datavalue":{"value":{"amount":"+0.8518173","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":"Q1814097$1C15A474-93F5-4AE7-855D-860CE9141D9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69a6f48b5b10d4b098acb522b8cde5258e12cccd","datavalue":{"value":{"entity-type":"item","numeric-id":2867103,"id":"Q2867103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b95a6065f16c23f65a17c60e656058fc9948a2dd","datavalue":{"value":{"amount":"+0.85181713","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":"Q1814097$02259CB0-15C7-43D0-9642-457C29F7A0C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee69a90fd842670f6dc67cc7f88550858411c34a","datavalue":{"value":{"entity-type":"item","numeric-id":4252281,"id":"Q4252281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f18cde71d5eed79d0d2432e3419790359de13171","datavalue":{"value":{"amount":"+0.8514906","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":"Q1814097$2CBB2E59-6B2D-457F-BACA-3BE8F767EC82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9c5352155c638e3f22bcb667f1a1af163f4e9e2","datavalue":{"value":{"entity-type":"item","numeric-id":2709795,"id":"Q2709795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f18cde71d5eed79d0d2432e3419790359de13171","datavalue":{"value":{"amount":"+0.8514906","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":"Q1814097$03AB02AD-BB00-4C8C-B934-E3A07E6F07CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f2bb04d435f12f34be6dd0a50a7f13352e9650a","datavalue":{"value":{"entity-type":"item","numeric-id":2169943,"id":"Q2169943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"825d3a6d4e1ea517255e993cdee7fa966e80a13f","datavalue":{"value":{"amount":"+0.8508433","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":"Q1814097$86D2DD52-1DDF-44F3-A02F-8FFF92F1FAAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db288ba56a9887e2bbbbd6ee9c02a51583c5aaa1","datavalue":{"value":{"entity-type":"item","numeric-id":1327029,"id":"Q1327029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fe3f59a18300555cd1fa4de36c88730831d4f24","datavalue":{"value":{"amount":"+0.8436686","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":"Q1814097$70DF574E-1933-4176-B947-66C210BE2385","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An efficient algorithm for finding a two-pair, and its applications","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_efficient_algorithm_for_finding_a_two-pair,_and_its_applications"}}}}}