Publication Information

{'id': 'https://openalex.org/W2011824743', 'doi': 'https://doi.org/10.1145/195058.195084', 'title': 'A randomized linear-time algorithm for finding minimum spanning trees', 'display_name': 'A randomized linear-time algorithm for finding minimum spanning trees', 'publication_year': 1994, 'publication_date': '1994-01-01', 'ids': {'openalex': 'https://openalex.org/W2011824743', 'doi': 'https://doi.org/10.1145/195058.195084', 'mag': '2011824743'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/195058.195084', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'proceedings-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/A5035567880', 'display_name': 'Philip N. Klein', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I27804330', 'display_name': 'Brown University', 'ror': 'https://ror.org/05gq02987', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I27804330']}, {'id': 'https://openalex.org/I196272386', 'display_name': 'Providence College', 'ror': 'https://ror.org/00rxpqe74', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I196272386']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Philip N. Klein', 'raw_affiliation_strings': ['Department of Computer Science, Brown University, Providence, RI,'], 'affiliations': [{'raw_affiliation_string': 'Department of Computer Science, Brown University, Providence, RI,', 'institution_ids': ['https://openalex.org/I27804330', 'https://openalex.org/I196272386']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5051027549', 'display_name': 'Robert E. Tarjan', 'orcid': 'https://orcid.org/0000-0001-7505-5768'}, 'institutions': [{'id': 'https://openalex.org/I20089843', 'display_name': 'Princeton University', 'ror': 'https://ror.org/00hx57361', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I20089843']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'Robert E. Tarjan', 'raw_affiliation_strings': ['Department of Computer Science, Princeton University, Princeton, NJ and NEC Research Institute, Princeton, NJ#TAB#'], 'affiliations': [{'raw_affiliation_string': 'Department of Computer Science, Princeton University, Princeton, NJ and NEC Research Institute, Princeton, NJ#TAB#', 'institution_ids': ['https://openalex.org/I20089843']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 3, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 4.039, 'has_fulltext': True, 'fulltext_origin': 'ngrams', 'cited_by_count': 53, 'citation_normalized_percentile': {'value': 0.864802, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 92, 'max': 93}, 'biblio': {'volume': None, 'issue': None, 'first_page': None, 'last_page': None}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.9998, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, '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/T10720', 'display_name': 'Complexity and Algorithms in Graphs', 'score': 0.9998, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, '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/T10374', 'display_name': 'Advanced Graph Theory Research', 'score': 0.9996, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, '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/T10142', 'display_name': 'Formal Methods in Verification', 'score': 0.9969, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/randomized-algorithm', 'display_name': 'Randomized Algorithm', 'score': 0.5197832}, {'id': 'https://openalex.org/keywords/prims-algorithm', 'display_name': "Prim's algorithm", 'score': 0.49234354}, {'id': 'https://openalex.org/keywords/reverse-delete-algorithm', 'display_name': 'Reverse-delete algorithm', 'score': 0.45841098}], 'concepts': [{'id': 'https://openalex.org/C13743678', 'wikidata': 'https://www.wikidata.org/wiki/Q240464', 'display_name': 'Minimum spanning tree', 'level': 2, 'score': 0.67488277}, {'id': 'https://openalex.org/C63645285', 'wikidata': 'https://www.wikidata.org/wiki/Q797860', 'display_name': "Kruskal's algorithm", 'level': 3, 'score': 0.5351297}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.530513}, {'id': 'https://openalex.org/C128669082', 'wikidata': 'https://www.wikidata.org/wiki/Q583461', 'display_name': 'Randomized algorithm', 'level': 2, 'score': 0.5197832}, {'id': 'https://openalex.org/C1649724', 'wikidata': 'https://www.wikidata.org/wiki/Q470813', 'display_name': "Prim's algorithm", 'level': 4, 'score': 0.49234354}, {'id': 'https://openalex.org/C64331007', 'wikidata': 'https://www.wikidata.org/wiki/Q831672', 'display_name': 'Spanning tree', 'level': 2, 'score': 0.48959333}, {'id': 'https://openalex.org/C199346575', 'wikidata': 'https://www.wikidata.org/wiki/Q4925151', 'display_name': 'Reverse-delete algorithm', 'level': 4, 'score': 0.45841098}, {'id': 'https://openalex.org/C311688', 'wikidata': 'https://www.wikidata.org/wiki/Q2393193', 'display_name': 'Time complexity', 'level': 2, 'score': 0.44684827}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.44109622}, {'id': 'https://openalex.org/C65949645', 'wikidata': 'https://www.wikidata.org/wiki/Q5283163', 'display_name': 'Distributed minimum spanning tree', 'level': 3, 'score': 0.43770075}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.36388415}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.2842612}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1145/195058.195084', 'pdf_url': None, 'source': None, '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': 19, 'referenced_works': ['https://openalex.org/W1512709563', 'https://openalex.org/W1513400187', 'https://openalex.org/W1570068679', 'https://openalex.org/W1965680834', 'https://openalex.org/W1971680255', 'https://openalex.org/W1978099551', 'https://openalex.org/W1982512167', 'https://openalex.org/W1996641400', 'https://openalex.org/W2023658462', 'https://openalex.org/W2041786457', 'https://openalex.org/W2042587503', 'https://openalex.org/W2068871408', 'https://openalex.org/W2087216833', 'https://openalex.org/W2133612817', 'https://openalex.org/W2152506249', 'https://openalex.org/W2156372444', 'https://openalex.org/W2164485560', 'https://openalex.org/W2167630072', 'https://openalex.org/W3161781519'], 'related_works': ['https://openalex.org/W4387896093', 'https://openalex.org/W4380840098', 'https://openalex.org/W4242086819', 'https://openalex.org/W3011323517', 'https://openalex.org/W2899787781', 'https://openalex.org/W2589768050', 'https://openalex.org/W2387385213', 'https://openalex.org/W2381121915', 'https://openalex.org/W2371157450', 'https://openalex.org/W2074214908'], 'abstract_inverted_index': {'Article': [0], 'A': [1], 'randomized': [2], 'linear-time': [3], 'algorithm': [4], 'for': [5], 'finding': [6], 'minimum': [7], 'spanning': [8], 'trees': [9], 'Share': [10], 'on': [11, 79, 130], 'Authors:': [12], 'Philip': [13], 'N.': [14], 'Klein': [15], 'Department': [16, 24, 37, 51], 'of': [17, 25, 38, 52, 73, 81], 'Computer': [18, 26, 39, 53], 'Science,': [19, 27, 40, 54], 'Brown': [20, 28], 'University,': [21, 29, 42, 56], 'Providence,': [22, 30], 'RI': [23], 'RIView': [31], 'Profile': [32, 65], ',': [33], 'Robert': [34], 'E.': [35], 'Tarjan': [36], 'Princeton': [41, 55], 'Princeton,': [43, 49, 57, 63], 'NJ': [44, 50, 58], 'and': [45, 59, 107], 'NEC': [46, 60], 'Research': [47, 61], 'Institute,': [48, 62], 'NJView': [64], 'Authors': [66], 'Info': [67], '&': [68], 'Claims': [69], 'STOC': [70], "'94:": [71], 'Proceedings': [72], 'the': [74, 131], 'twenty-sixth': [75], 'annual': [76], 'ACM': [77], 'symposium': [78], 'Theory': [80], 'ComputingMay': [82], '1994': [83], 'Pages': [84], '9–15https://doi.org/10.1145/195058.195084Online:23': [85], 'May': [86], '1994Publication': [87], 'History': [88], '19citation613DownloadsMetricsTotal': [89], 'Citations19Total': [90], 'Downloads613Last': [91], '12': [92], 'Months15Last': [93], '6': [94], 'weeks2': [95], 'Get': [96], 'Citation': [97, 99, 136], 'AlertsNew': [98, 135], 'Alert': [100], 'added!This': [101], 'alert': [102, 127], 'has': [103, 122], 'been': [104, 123], 'successfully': [105], 'added': [106], 'will': [108, 112], 'be': [109, 113], 'sent': [110], 'to:You': [111], 'notified': [114], 'whenever': [115], 'a': [116, 148], 'record': [117], 'that': [118], 'you': [119], 'have': [120], 'chosen': [121], 'cited.To': [124], 'manage': [125], 'your': [126, 141], 'preferences,': [128], 'click': [129], 'button': [132], 'below.Manage': [133], 'my': [134], 'Alert!Please': [137], 'log': [138], 'in': [139], 'to': [140, 144, 146], 'account': [142], 'Save': [143], 'BinderSave': [145], 'BinderCreate': [147], 'New': [149], 'BinderNameCancelCreateExport': [150], 'CitationPublisher': [151], 'SiteGet': [152], 'Access': [153]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2011824743', 'counts_by_year': [{'year': 2015, 'cited_by_count': 1}], 'updated_date': '2024-12-17T07:07:26.947342', 'created_date': '2016-06-24'}