Publication Information

{'id': 'https://openalex.org/W2030917606', 'doi': 'https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<205::aid-rsa11>3.0.co;2-7', 'title': 'On the all-pairs shortest-path algorithm of Moffat and Takaoka', 'display_name': 'On the all-pairs shortest-path algorithm of Moffat and Takaoka', 'publication_year': 1997, 'publication_date': '1997-01-01', 'ids': {'openalex': 'https://openalex.org/W2030917606', 'doi': 'https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<205::aid-rsa11>3.0.co;2-7', 'mag': '2030917606'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<205::aid-rsa11>3.0.co;2-7', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S59667848', 'display_name': 'Random Structures and Algorithms', 'issn_l': '1042-9832', 'issn': ['1042-9832', '1098-2418'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310320595', 'host_organization_name': 'Wiley', 'host_organization_lineage': ['https://openalex.org/P4310320595'], 'host_organization_lineage_names': ['Wiley'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'journal-article', 'indexed_in': ['crossref'], 'open_access': {'is_oa': False, 'oa_status': 'closed', 'oa_url': None, 'any_repository_has_fulltext': False}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5010961023', 'display_name': 'Kurt Mehlhorn', 'orcid': 'https://orcid.org/0000-0003-4020-4334'}, 'institutions': [{'id': 'https://openalex.org/I149899117', 'display_name': 'Max Planck Society', 'ror': 'https://ror.org/01hhn8329', 'country_code': 'DE', 'type': 'nonprofit', 'lineage': ['https://openalex.org/I149899117']}], 'countries': ['DE'], 'is_corresponding': False, 'raw_author_name': 'Kurt Mehlhorn', 'raw_affiliation_strings': ['Algorithms and Complexity, MPI for Informatics, Max Planck Society'], 'affiliations': [{'raw_affiliation_string': 'Algorithms and Complexity, MPI for Informatics, Max Planck Society', 'institution_ids': ['https://openalex.org/I149899117']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5056708884', 'display_name': 'Volker Priebe', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I149899117', 'display_name': 'Max Planck Society', 'ror': 'https://ror.org/01hhn8329', 'country_code': 'DE', 'type': 'nonprofit', 'lineage': ['https://openalex.org/I149899117']}], 'countries': ['DE'], 'is_corresponding': False, 'raw_author_name': 'Volker Priebe', 'raw_affiliation_strings': ['Algorithms and Complexity, MPI for Informatics, Max Planck Society'], 'affiliations': [{'raw_affiliation_string': 'Algorithms and Complexity, MPI for Informatics, Max Planck Society', 'institution_ids': ['https://openalex.org/I149899117']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 1, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': {'value': 4330, 'currency': 'USD', 'value_usd': 4330, 'provenance': 'doaj'}, 'apc_paid': None, 'fwci': 3.172, 'has_fulltext': True, 'fulltext_origin': 'ngrams', 'cited_by_count': 22, 'citation_normalized_percentile': {'value': 0.82877, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 85, 'max': 86}, 'biblio': {'volume': '10', 'issue': '1-2', 'first_page': '205', 'last_page': '220'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T11269', 'display_name': 'Algorithms and Data Compression', 'score': 0.9981, 'subfield': {'id': 'https://openalex.org/subfields/1702', 'display_name': 'Artificial Intelligence'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, 'topics': [{'id': 'https://openalex.org/T11269', 'display_name': 'Algorithms and Data Compression', 'score': 0.9981, 'subfield': {'id': 'https://openalex.org/subfields/1702', 'display_name': 'Artificial Intelligence'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T12288', 'display_name': 'Optimization and Search Problems', 'score': 0.9971, 'subfield': {'id': 'https://openalex.org/subfields/1705', 'display_name': 'Computer Networks and Communications'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T12072', 'display_name': 'Machine Learning and Algorithms', 'score': 0.993, 'subfield': {'id': 'https://openalex.org/subfields/1702', 'display_name': 'Artificial Intelligence'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [], 'concepts': [{'id': 'https://openalex.org/C2778805511', 'wikidata': 'https://www.wikidata.org/wiki/Q1713', 'display_name': 'Citation', 'level': 2, 'score': 0.49756554}, {'id': 'https://openalex.org/C2777735758', 'wikidata': 'https://www.wikidata.org/wiki/Q817765', 'display_name': 'Path (computing)', 'level': 2, 'score': 0.4362756}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.4324044}, {'id': 'https://openalex.org/C121332964', 'wikidata': 'https://www.wikidata.org/wiki/Q413', 'display_name': 'Physics', 'level': 0, 'score': 0.4234904}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.3918856}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.3896917}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.37665224}, {'id': 'https://openalex.org/C161191863', 'wikidata': 'https://www.wikidata.org/wiki/Q199655', 'display_name': 'Library science', 'level': 1, 'score': 0.32131192}, {'id': 'https://openalex.org/C199360897', 'wikidata': 'https://www.wikidata.org/wiki/Q9143', 'display_name': 'Programming language', 'level': 1, 'score': 0.052922755}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<205::aid-rsa11>3.0.co;2-7', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S59667848', 'display_name': 'Random Structures and Algorithms', 'issn_l': '1042-9832', 'issn': ['1042-9832', '1098-2418'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310320595', 'host_organization_name': 'Wiley', 'host_organization_lineage': ['https://openalex.org/P4310320595'], 'host_organization_lineage_names': ['Wiley'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}], 'best_oa_location': None, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 0, 'referenced_works': [], 'related_works': ['https://openalex.org/W4391375266', 'https://openalex.org/W4317642157', 'https://openalex.org/W4239542068', 'https://openalex.org/W2363440148', 'https://openalex.org/W2317510431', 'https://openalex.org/W2073681303', 'https://openalex.org/W2053286651', 'https://openalex.org/W2051487156', 'https://openalex.org/W1974749013', 'https://openalex.org/W134931362'], 'abstract_inverted_index': {'Random': [0, 284], 'Structures': [1], '&': [2, 281], 'AlgorithmsVolume': [3], '10,': [4, 287, 450], 'Issue': [5], '1-2': [6], 'p.': [7], '205-220': [8, 804], 'On': [9, 535, 575], 'the': [10, 123, 170, 180, 209, 348, 387, 390, 512, 536, 576, 761, 764], 'all-pairs': [11, 210, 518, 577], 'shortest-path': [12, 211, 269, 296, 440], 'algorithm': [13, 297, 580, 617, 652, 726], 'of': [14, 117, 154, 164, 177, 188, 240, 255, 313, 377, 389, 428, 455, 465, 478, 485, 498, 529, 538, 566, 581, 631, 667, 675, 687, 717, 735, 763, 778, 796], 'Moffat': [15, 582, 608, 643], 'and': [16, 152, 156, 168, 175, 194, 342, 407, 413, 435, 489, 507, 572, 583, 609, 644, 682, 690, 698], 'Takaoka†': [17], 'Kurt': [18, 20, 62, 64], 'Mehlhorn,': [19, 63], 'Mehlhorn': [21, 65, 571], 'Max-Planck-Institut': [22, 41, 66, 85, 354], 'für': [23, 42, 49, 67, 86, 93, 355], 'Informatik,': [24, 43, 50, 68, 87, 94, 356], 'Im': [25, 44, 51, 69, 88, 95], 'Stadtwald,': [26, 45, 52, 70, 89, 96], '66123': [27, 46, 53, 71, 90, 97], 'Saarbrücken,': [28, 47, 54, 72, 91, 98], 'GermanySearch': [29, 55, 73, 99], 'for': [30, 56, 74, 100, 236, 251, 442, 463, 517, 680, 727], 'more': [31, 57, 75, 101], 'papers': [32, 58, 76, 102], 'by': [33, 59, 77, 103], 'this': [34, 60, 78, 104, 118, 189], 'authorVolker': [35, 79], 'Priebe,': [36, 80, 341, 574], 'Corresponding': [37, 81], 'Author': [38, 82], 'Volker': [39, 83], 'Priebe': [40, 84], 'GermanyMax-Planck-Institut': [48, 92], 'author': [61, 105], 'First': [106], 'published:': [107], '13': [108, 112, 606], 'January': [109], '2000': [110], 'https://doi.org/10.1002/(SICI)1098-2418(199701/03)10:1/2<205::AID-RSA11>3.0.CO;2-7Citations:': [111], '†': [113], 'A': [114, 295, 320, 724, 756], 'preliminary': [115], 'version': [116, 163, 187], 'paper': [119], 'was': [120], 'presented': [121], 'at': [122], 'Third': [124], 'Annual': [125, 627], 'European': [126], 'Symposium': [127, 628], 'on': [128, 243, 322, 386, 629, 760], 'Algorithms,': [129], 'Corfu,': [130], 'Greece,': [131], '1995': [132], '[12].': [133], 'AboutPDF': [134], 'ToolsRequest': [135], 'permissionExport': [136], 'citationAdd': [137], 'to': [138, 160, 183, 207, 231, 267, 273], 'favoritesTrack': [139], 'citation': [140], 'ShareShare': [141], 'Give': [142], 'accessShare': [143, 146], 'full': [144], 'text': [145], 'full-text': [147, 162, 186], 'accessPlease': [148], 'review': [149, 205], 'our': [150], 'Terms': [151, 174], 'Conditions': [153, 176], 'Use': [155], 'check': [157], 'box': [158], 'below': [159, 182], 'share': [161, 184], 'article.I': [165], 'have': [166], 'read': [167], 'accept': [169], 'Wiley': [171, 280], 'Online': [172], 'Library': [173], 'UseShareable': [178], 'LinkUse': [179], 'link': [181], 'a': [185, 200, 214, 237, 252, 274, 733], 'article': [190], 'with': [191, 218, 233, 264, 271, 298, 327, 444, 618, 653], 'your': [192], 'friends': [193], 'colleagues.': [195], 'Learn': [196], 'more.Copy': [197], 'URL': [198], 'Share': [199], 'linkShare': [201], 'onEmailFacebookTwitterLinkedInRedditWechat': [202], 'Abstract': [203], 'We': [204, 247], 'how': [206], 'solve': [208], 'problem': [212, 441], 'in': [213, 221, 325, 416, 541, 543, 585, 594, 685, 706, 732, 738, 786], 'nonnegatively': [215, 244], 'weighted': [216, 245], 'digraph': [217], 'n': [219, 303], 'vertices': [220], 'expected': [222, 299, 619, 654], 'time': [223, 261, 300, 515, 621, 655, 740], 'O(n2': [224, 301, 622, 656, 741], 'log': [225, 259, 302, 623, 657], 'n).': [226], 'This': [227], 'bound': [228, 759], 'is': [229, 262], 'shown': [230], 'hold': [232], 'high': [234, 265], 'probability': [235, 241, 256, 266, 787], 'wide': [238], 'class': [239, 254], 'distributions': [242], 'digraphs.': [246], 'also': [248], 'prove': [249], 'that,': [250], 'large': [253], 'distributions,': [257], 'Ω(n': [258], 'n)': [260], 'necessary': [263], 'compute': [268], 'distances': [270], 'respect': [272], 'single': [275], 'source.': [276], '©': [277], '1997': [278], 'John': [279], 'Sons,': [282], 'Inc.': [283], 'Struct.': [285], 'Alg.,': [286], '205–220': [288], '(1997)': [289], 'References': [290], '1': [291], 'P.': [292, 589, 721], 'A.': [293, 432, 607, 642], 'Bloniarz,': [294], 'log*n),': [304], 'SIAM': [305, 394, 521, 659, 744], 'J': [306], 'Comput.,': [307, 396, 523, 661, 746], '12,': [308], '588–600': [309], '(1983).': [310], '10.1137/0212039': [311], 'Web': [312, 376, 427, 454, 477, 497, 528, 565, 666, 716, 777, 795], 'Science®Google': [314, 378, 429, 456, 479, 499, 530, 567, 668, 718, 779, 797], 'Scholar': [315, 336, 361, 379, 402, 430, 457, 480, 500, 531, 568, 605, 640, 669, 719, 752, 780, 798], '2': [316], 'E.': [317, 409, 700], 'W.': [318, 364, 459], 'Dijkstra,': [319], 'note': [321], 'two': [323], 'problems': [324], 'connexion': [326], 'graphs,': [328], 'Numer.': [329], 'Math.,': [330, 449], '1,': [331], '269–271': [332], '(1959)': [333], '10.1007/BF01386390': [334], 'Google': [335, 360, 401, 604, 639, 751], '3': [337], 'D.': [338, 343, 502, 505], 'Dubhashi,': [339], 'V.': [340, 573, 696], 'Ranjan,': [344], 'Negative': [345], 'dependence': [346], 'through': [347], 'FKG': [349], 'inequality,': [350], 'Research': [351], 'Report': [352], 'MPI-I-96-1-020,': [353], 'Saar-brücken,': [357], 'August': [358], '(1996).': [359], '4': [362], 'R.': [363, 408, 437, 503, 671], 'Floyd,': [365], 'Algorithm': [366], '97:': [367], 'shortest': [368, 391, 519, 578, 615, 650, 730, 767], 'path,': [369], 'Commun.': [370], 'ACM,': [371, 422], '5,': [372, 397], '345': [373], '(1962).': [374], '10.1145/367766.368168': [375], '5': [380], 'M.': [381, 404, 433, 482, 722], 'L.': [382, 405], 'Fredman,': [383], 'New': [384], 'bounds': [385, 516], 'complexity': [388, 762], 'path': [392, 579, 616, 651, 768], 'problem,': [393, 769], 'J.': [395, 421, 469, 509, 522, 547, 660, 745, 790], '83–89': [398], '(1976).': [399], '10.1137/0205006': [400], '6': [403], 'Fredman': [406], 'Tarjan,': [410], 'Fibonacci': [411], 'heaps': [412], 'their': [414], 'uses': [415], 'improved': [417], 'network': [418], 'optimization': [419], 'algorithms,': [420], '34,': [423], '596–615': [424], '(1987).': [425, 664], '10.1145/28869.28874': [426], '7': [431], 'Frieze': [434], 'G.': [436], 'Grimmett,': [438], 'The': [439, 673], 'graphs': [443], 'random': [445, 467], 'arc-lengths,': [446], 'Discrete': [447], 'Appl.': [448], '57–77': [451], '(1985).': [452], '10.1016/0166-218X(85)90059-9': [453], '8': [458], 'Hoeffding,': [460], 'Probability': [461], 'inequalities': [462], 'sums': [464], 'bounded': [466, 539], 'variables,': [468], 'Am.': [470], 'Stat.': [471], 'Assoc.,': [472], '58,': [473], '13–30': [474], '(1963).': [475], '10.1080/01621459.1963.10500830': [476], '9': [481], 'Hofri,': [483], 'Analysis': [484], 'Algorithms:': [486], 'Computational': [487], 'Methods': [488], 'Mathematical': [490, 551], 'Tools,': [491], 'Oxford': [492], 'University': [493, 558], 'Press,': [494, 559], 'Oxford,': [495], '1995.': [496], '10': [501], 'Karger,': [504], 'Koller,': [506], 'S.': [508], 'Phillips,': [510], 'Finding': [511], 'hidden': [513], 'path:': [514], 'paths,': [520], '22,': [524, 792], '1199–1217': [525], '(1993).': [526], '10.1137/0222071': [527], '11': [532], 'C.': [533, 699], 'McDiarmid,': [534], 'method': [537], 'differences,': [540], 'Surveys': [542], 'Combinatorics,': [544], '1989,': [545, 561], '(': [546, 588, 694], 'Siemons,': [548], 'Ed.),': [549, 591], 'London': [550], 'Society': [552], 'Lecture': [553, 592, 704], 'Note': [554], 'Series': [555], '141,': [556], 'Cambridge': [557], 'Cambridge,': [560], 'pp.': [562, 601, 637, 713], '148–188.': [563], '10.1017/CBO9781107359949.008': [564], '12': [569], 'K.': [570, 695], 'Takaoka,': [584, 611, 646, 755], 'Algorithms–ESA': [586], "'95": [587], 'Spirakis,': [590], 'Notes': [593, 705], 'Computer': [595, 632, 692, 707], 'Science': [596, 708], '979,': [597], 'Springer-Verlag,': [598, 710], 'Berlin,': [599, 711], '1995,': [600], '185–198.': [602], '10.1007/3-540-60313-1_143': [603], 'T.': [610, 645, 754], 'An': [612, 647], 'all': [613, 648, 729, 765], 'pairs': [614, 649, 766], 'running': [620], 'n),': [624, 658, 743], 'Proc.': [625], '26th': [626], 'Foundations': [630, 686], 'Science,': [633, 693], 'Portland,': [634], 'OR,': [635], '1985,': [636], '101–105.': [638], '14': [641], '16,': [662], '1023–1031': [663], '10.1137/0216065': [665], '15': [670], 'Raman,': [672], 'power': [674], 'collision:': [676], 'randomized': [677], 'parallel': [678], 'algorithms': [679], 'chaining': [681], 'integer': [683], 'sorting,': [684], 'Software': [688], 'Technology': [689], 'Theoretical': [691], 'Nori': [697], 'Veni': [701], 'Madhavan,': [702], 'Eds.),': [703], '472,': [709], '1990,': [712], '161–175.': [714], '10.1007/BFb0018363': [715], '16': [720], 'Spira,': [723], 'new': [725, 757], 'finding': [728], 'paths': [731], 'graph': [734], 'positive': [736], 'arcs': [737], 'average': [739], 'log2': [742], '2,': [747], '28–32': [748], '(1973).': [749], '10.1137/0202004': [750], '17': [753], 'upper': [758], 'Inf.': [770], 'Process.': [771], 'Lett.,': [772], '43,': [773], '195–199': [774], '(1992).': [775], '10.1016/0020-0190(92)90200-F': [776], '18': [781], 'H.': [782], 'Thorisson,': [783], 'Coupling': [784], 'methods': [785], 'theory,': [788], 'Scand.': [789], 'Stat.,': [791], '159–182': [793], '(1995).': [794], 'Citing': [799], 'Literature': [800], 'Volume10,': [801], 'Issue1-2January': [802], '1997Pages': [803], 'ReferencesRelatedInformation': [805]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2030917606', 'counts_by_year': [{'year': 2015, 'cited_by_count': 2}, {'year': 2014, 'cited_by_count': 1}, {'year': 2013, 'cited_by_count': 2}, {'year': 2012, 'cited_by_count': 1}], 'updated_date': '2024-12-13T13:47:21.877757', 'created_date': '2016-06-24'}