Publication Information

{'id': 'https://openalex.org/W3013721100', 'doi': 'https://doi.org/10.4230/lipics.stacs.2020.11', 'title': 'An FPT Algorithm for Minimum Additive Spanner Problem.', 'display_name': 'An FPT Algorithm for Minimum Additive Spanner Problem.', 'publication_year': 2020, 'publication_date': '2020-01-01', 'ids': {'openalex': 'https://openalex.org/W3013721100', 'doi': 'https://doi.org/10.4230/lipics.stacs.2020.11', 'mag': '3013721100'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.4230/LIPIcs.STACS.2020.11', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306421002', 'display_name': 'Symposium on Theoretical Aspects of Computer Science', 'issn_l': None, 'issn': None, 'is_oa': False, 'is_in_doaj': False, 'is_core': False, 'host_organization': None, 'host_organization_name': None, 'host_organization_lineage': [], 'host_organization_lineage_names': [], 'type': 'conference'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'proceedings-article', 'indexed_in': [], '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/A5074548000', 'display_name': 'Yusuke Kobayashi', 'orcid': 'https://orcid.org/0000-0001-9478-7307'}, 'institutions': [{'id': 'https://openalex.org/I22299242', 'display_name': 'Kyoto University', 'ror': 'https://ror.org/02kpeqv85', 'country_code': 'JP', 'type': 'education', 'lineage': ['https://openalex.org/I22299242']}], 'countries': ['JP'], 'is_corresponding': True, 'raw_author_name': 'Yusuke Kobayashi', 'raw_affiliation_strings': ['Kyoto University, Kyoto, Japan'], 'affiliations': [{'raw_affiliation_string': 'Kyoto University, Kyoto, Japan', 'institution_ids': ['https://openalex.org/I22299242']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 1, 'corresponding_author_ids': ['https://openalex.org/A5074548000'], 'corresponding_institution_ids': ['https://openalex.org/I22299242'], 'apc_list': None, 'apc_paid': None, 'fwci': 0.465, 'has_fulltext': False, 'cited_by_count': 2, 'citation_normalized_percentile': {'value': 0.307846, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 69, 'max': 73}, 'biblio': {'volume': None, 'issue': None, 'first_page': '16', '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.9984, '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.9984, '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.9972, '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/T12288', 'display_name': 'Optimization and Search Problems', 'score': 0.9922, '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'}}], 'keywords': [{'id': 'https://openalex.org/keywords/spanner', 'display_name': 'Spanner', 'score': 0.95935065}], 'concepts': [{'id': 'https://openalex.org/C2779585601', 'wikidata': 'https://www.wikidata.org/wiki/Q4049850', 'display_name': 'Spanner', 'level': 2, 'score': 0.95935065}, {'id': 'https://openalex.org/C165464430', 'wikidata': 'https://www.wikidata.org/wiki/Q1570441', 'display_name': 'Parameterized complexity', 'level': 2, 'score': 0.8017937}, {'id': 'https://openalex.org/C42747912', 'wikidata': 'https://www.wikidata.org/wiki/Q1048447', 'display_name': 'Multiplicative function', 'level': 2, 'score': 0.7325621}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.6700789}, {'id': 'https://openalex.org/C148764684', 'wikidata': 'https://www.wikidata.org/wiki/Q621751', 'display_name': 'Approximation algorithm', 'level': 2, 'score': 0.57602686}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.57142633}, {'id': 'https://openalex.org/C132525143', 'wikidata': 'https://www.wikidata.org/wiki/Q141488', 'display_name': 'Graph', 'level': 2, 'score': 0.48343432}, {'id': 'https://openalex.org/C97137487', 'wikidata': 'https://www.wikidata.org/wiki/Q729138', 'display_name': 'Integer (computer science)', 'level': 2, 'score': 0.4346994}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.40003732}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.32896024}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.29230404}, {'id': 'https://openalex.org/C134306372', 'wikidata': 'https://www.wikidata.org/wiki/Q7754', 'display_name': 'Mathematical analysis', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C120314980', 'wikidata': 'https://www.wikidata.org/wiki/Q180634', 'display_name': 'Distributed computing', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C199360897', 'wikidata': 'https://www.wikidata.org/wiki/Q9143', 'display_name': 'Programming language', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.4230/LIPIcs.STACS.2020.11', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306421002', 'display_name': 'Symposium on Theoretical Aspects of Computer Science', 'issn_l': None, 'issn': None, 'is_oa': False, 'is_in_doaj': False, 'is_core': False, 'host_organization': None, 'host_organization_name': None, 'host_organization_lineage': [], 'host_organization_lineage_names': [], 'type': 'conference'}, '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/W3127121181', 'https://openalex.org/W3117774579', 'https://openalex.org/W3102537597', 'https://openalex.org/W3035713054', 'https://openalex.org/W2953285790', 'https://openalex.org/W2949148389', 'https://openalex.org/W2919689475', 'https://openalex.org/W2903563585', 'https://openalex.org/W2763773774', 'https://openalex.org/W2515547009', 'https://openalex.org/W2143043241', 'https://openalex.org/W1998215513', 'https://openalex.org/W1993617716', 'https://openalex.org/W1992976178', 'https://openalex.org/W1986075609', 'https://openalex.org/W1887178672', 'https://openalex.org/W1837754425', 'https://openalex.org/W1746024445', 'https://openalex.org/W1494854198', 'https://openalex.org/W1481813913'], 'abstract_inverted_index': {'For': [0], 'a': [1, 6, 15, 53, 114, 130, 134, 149], 'positive': [2], 'integer': [3], 't': [4], 'and': [5, 87, 132, 154], 'graph': [7], 'G,': [8], 'an': [9, 43, 155], 'additive': [10, 44, 76, 156], 't-spanner': [11, 45], 'of': [12, 25, 50, 70, 109, 117, 124], 'G': [13], 'is': [14, 27, 40, 57, 83, 127], 'spanning': [16], 'subgraph': [17], 'in': [18, 52, 120], 'which': [19, 56, 121, 160], 'the': [20, 30, 47, 78, 101, 107, 118, 122, 145], 'distance': [21, 32], 'between': [22], 'every': [23], 'pair': [24], 'vertices': [26], 'at': [28], 'most': [29], 'original': [31], 'plus': [33], 't.': [34], 'The': [35], 'Minimum': [36, 79, 102], 'Additive': [37, 80, 103], 't-Spanner': [38, 81, 104], 'Problem': [39, 82, 105], 'to': [41, 59, 65, 85, 144], 'find': [42], 'with': [46, 75, 147], 'minimum': [48], 'number': [49, 123], 'edges': [51, 126], 'given': [54], 'graph,': [55], 'known': [58, 93], 'be': [60], 'NP-hard.': [61], 'Since': [62], 'we': [63, 73, 99, 161], 'need': [64], 'care': [66], 'about': [67], 'global': [68], 'properties': [69], 'graphs': [71], 'when': [72], 'deal': [74], 't-spanners,': [77], 'hard': [84], 'handle': [86], 'hence': [88], 'only': [89], 'few': [90], 'results': [91], 'are': [92], 'for': [94, 137], 'it.': [95, 138], 'In': [96], 'this': [97], 'paper,': [98], 'study': [100], 'from': [106], 'viewpoint': [108], 'parameterized': [110, 115], 'complexity.': [111], 'We': [112, 139], 'formulate': [113], 'version': [116], 'problem': [119], 'removed': [125], 'regarded': [128], 'as': [129], 'parameter,': [131], 'give': [133], 'fixed-parameter': [135], 'algorithm': [136], 'also': [140], 'extend': [141], 'our': [142], 'result': [143], 'case': [146], 'both': [148], 'multiplicative': [150], 'approximation': [151, 157], 'factor': [152], 'α': [153], 'parameter': [158], 'β,': [159], 'call': [162], '(α,': [163], 'β)-spanners.': [164]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W3013721100', 'counts_by_year': [{'year': 2021, 'cited_by_count': 2}], 'updated_date': '2024-12-27T15:07:36.586012', 'created_date': '2020-04-03'}