Get quick answers to your questions about the article from our AI researcher chatbot
{'id': 'https://openalex.org/W1617257399', 'doi': 'https://doi.org/10.1007/s00453-015-0083-x', 'title': 'A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs', 'display_name': 'A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs', 'publication_year': 2015, 'publication_date': '2015-11-16', 'ids': {'openalex': 'https://openalex.org/W1617257399', 'doi': 'https://doi.org/10.1007/s00453-015-0083-x', 'mag': '1617257399'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1007/s00453-015-0083-x', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S89324355', 'display_name': 'Algorithmica', 'issn_l': '0178-4617', 'issn': ['0178-4617', '1432-0541'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319900', 'host_organization_name': 'Springer Science+Business Media', 'host_organization_lineage': ['https://openalex.org/P4310319965', 'https://openalex.org/P4310319900'], 'host_organization_lineage_names': ['Springer Nature', 'Springer Science+Business Media'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'journal-article', 'indexed_in': ['arxiv', 'crossref', 'datacite'], 'open_access': {'is_oa': True, 'oa_status': 'green', 'oa_url': 'https://arxiv.org/pdf/1310.6205', 'any_repository_has_fulltext': True}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5033238040', 'display_name': 'Stéphan Thomassé', 'orcid': 'https://orcid.org/0000-0002-7090-1790'}, 'institutions': [{'id': 'https://openalex.org/I113428412', 'display_name': 'École Normale Supérieure de Lyon', 'ror': 'https://ror.org/04zmssz18', 'country_code': 'FR', 'type': 'education', 'lineage': ['https://openalex.org/I113428412', 'https://openalex.org/I203339264']}, {'id': 'https://openalex.org/I185839726', 'display_name': 'Institut Universitaire de France', 'ror': 'https://ror.org/055khg266', 'country_code': 'FR', 'type': 'education', 'lineage': ['https://openalex.org/I185839726']}], 'countries': ['FR'], 'is_corresponding': False, 'raw_author_name': 'Stéphan Thomassé', 'raw_affiliation_strings': ['IUF - Institut Universitaire de France (Maison des Universités 103 Boulevard Saint-Michel 75005 Paris - France)', "MC2 - Modèles de calcul, Complexité, Combinatoire (ENS Lyon 46 allée d'Italie 69364 Lyon Cedex 07 - France)"], 'affiliations': [{'raw_affiliation_string': "MC2 - Modèles de calcul, Complexité, Combinatoire (ENS Lyon 46 allée d'Italie 69364 Lyon Cedex 07 - France)", 'institution_ids': ['https://openalex.org/I113428412']}, {'raw_affiliation_string': 'IUF - Institut Universitaire de France (Maison des Universités 103 Boulevard Saint-Michel 75005 Paris - France)', 'institution_ids': ['https://openalex.org/I185839726']}]}, {'author_position': 'middle', 'author': {'id': 'https://openalex.org/A5056688500', 'display_name': 'Nicolas Trotignon', 'orcid': 'https://orcid.org/0000-0003-1978-0687'}, 'institutions': [{'id': 'https://openalex.org/I113428412', 'display_name': 'École Normale Supérieure de Lyon', 'ror': 'https://ror.org/04zmssz18', 'country_code': 'FR', 'type': 'education', 'lineage': ['https://openalex.org/I113428412', 'https://openalex.org/I203339264']}], 'countries': ['FR'], 'is_corresponding': False, 'raw_author_name': 'Nicolas Trotignon', 'raw_affiliation_strings': ["MC2 - Modèles de calcul, Complexité, Combinatoire (ENS Lyon 46 allée d'Italie 69364 Lyon Cedex 07 - France)"], 'affiliations': [{'raw_affiliation_string': "MC2 - Modèles de calcul, Complexité, Combinatoire (ENS Lyon 46 allée d'Italie 69364 Lyon Cedex 07 - France)", 'institution_ids': ['https://openalex.org/I113428412']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5077118262', 'display_name': 'Kristina Vušković', 'orcid': 'https://orcid.org/0000-0003-3286-3145'}, 'institutions': [{'id': 'https://openalex.org/I130828816', 'display_name': 'University of Leeds', 'ror': 'https://ror.org/024mrxd33', 'country_code': 'GB', 'type': 'education', 'lineage': ['https://openalex.org/I130828816']}], 'countries': ['GB'], 'is_corresponding': False, 'raw_author_name': 'Kristina Vušković', 'raw_affiliation_strings': ['School of Computing [Leeds] (University of Leeds, Faculty of Engineering, Leeds LS2 9JT - United Kingdom)'], 'affiliations': [{'raw_affiliation_string': 'School of Computing [Leeds] (University of Leeds, Faculty of Engineering, Leeds LS2 9JT - United Kingdom)', 'institution_ids': ['https://openalex.org/I130828816']}]}], 'countries_distinct_count': 2, 'institutions_distinct_count': 3, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': {'value': 2290, 'currency': 'EUR', 'value_usd': 2890, 'provenance': 'doaj'}, 'apc_paid': None, 'fwci': 2.58, 'has_fulltext': True, 'fulltext_origin': 'pdf', 'cited_by_count': 24, 'citation_normalized_percentile': {'value': 0.85044, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 92, 'max': 93}, 'biblio': {'volume': '77', 'issue': '3', 'first_page': '619', 'last_page': '641'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10374', 'display_name': 'Graph Theory and Algorithms', 'score': 0.9999, '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/T10374', 'display_name': 'Graph Theory and Algorithms', 'score': 0.9999, '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/T11329', 'display_name': 'Limits and Structures in Graph Theory', 'score': 0.9988, 'subfield': {'id': 'https://openalex.org/subfields/2607', 'display_name': 'Discrete Mathematics and Combinatorics'}, 'field': {'id': 'https://openalex.org/fields/26', 'display_name': 'Mathematics'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T10720', 'display_name': 'Combinatorial Optimization and Complexity Theory', 'score': 0.9985, '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/graph-limits', 'display_name': 'Graph Limits', 'score': 0.531592}, {'id': 'https://openalex.org/keywords/fixed-parameter-algorithms', 'display_name': 'Fixed-Parameter Algorithms', 'score': 0.501588}, {'id': 'https://openalex.org/keywords/dominating-set', 'display_name': 'Dominating set', 'score': 0.43943253}, {'id': 'https://openalex.org/keywords/split-graph', 'display_name': 'Split graph', 'score': 0.43057287}], 'concepts': [{'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.72358805}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.722216}, {'id': 'https://openalex.org/C122818955', 'wikidata': 'https://www.wikidata.org/wiki/Q1060343', 'display_name': 'Independent set', 'level': 3, 'score': 0.6289172}, {'id': 'https://openalex.org/C311688', 'wikidata': 'https://www.wikidata.org/wiki/Q2393193', 'display_name': 'Time complexity', 'level': 2, 'score': 0.50017357}, {'id': 'https://openalex.org/C160446489', 'wikidata': 'https://www.wikidata.org/wiki/Q7226642', 'display_name': 'Polynomial kernel', 'level': 4, 'score': 0.4903126}, {'id': 'https://openalex.org/C34388435', 'wikidata': 'https://www.wikidata.org/wiki/Q2267362', 'display_name': 'Bounded function', 'level': 2, 'score': 0.46209398}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.4607732}, {'id': 'https://openalex.org/C146661039', 'wikidata': 'https://www.wikidata.org/wiki/Q2915204', 'display_name': 'Dominating set', 'level': 4, 'score': 0.43943253}, {'id': 'https://openalex.org/C8554925', 'wikidata': 'https://www.wikidata.org/wiki/Q3893853', 'display_name': 'Split graph', 'level': 5, 'score': 0.43057287}, {'id': 'https://openalex.org/C160446614', 'wikidata': 'https://www.wikidata.org/wiki/Q1322892', 'display_name': 'Chordal graph', 'level': 3, 'score': 0.40793192}, {'id': 'https://openalex.org/C132525143', 'wikidata': 'https://www.wikidata.org/wiki/Q141488', 'display_name': 'Graph', 'level': 2, 'score': 0.4059447}, {'id': 'https://openalex.org/C102192266', 'wikidata': 'https://www.wikidata.org/wiki/Q4545823', 'display_name': '1-planar graph', 'level': 4, 'score': 0.22799483}, {'id': 'https://openalex.org/C80899671', 'wikidata': 'https://www.wikidata.org/wiki/Q1304193', 'display_name': 'Vertex (graph theory)', 'level': 3, 'score': 0.19282463}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.130077}, {'id': 'https://openalex.org/C122280245', 'wikidata': 'https://www.wikidata.org/wiki/Q620622', 'display_name': 'Kernel method', 'level': 3, 'score': 0.12163088}, {'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/C154945302', 'wikidata': 'https://www.wikidata.org/wiki/Q11660', 'display_name': 'Artificial intelligence', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C12267149', 'wikidata': 'https://www.wikidata.org/wiki/Q282453', 'display_name': 'Support vector machine', 'level': 2, 'score': 0.0}], 'mesh': [], 'locations_count': 8, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1007/s00453-015-0083-x', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S89324355', 'display_name': 'Algorithmica', 'issn_l': '0178-4617', 'issn': ['0178-4617', '1432-0541'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319900', 'host_organization_name': 'Springer Science+Business Media', 'host_organization_lineage': ['https://openalex.org/P4310319965', 'https://openalex.org/P4310319900'], 'host_organization_lineage_names': ['Springer Nature', 'Springer Science+Business Media'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': False, 'landing_page_url': 'https://hal.science/hal-01482301', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306402512', 'display_name': 'HAL (Le Centre pour la Communication Scientifique Directe)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I1294671590', 'host_organization_name': 'Centre National de la Recherche Scientifique', 'host_organization_lineage': ['https://openalex.org/I1294671590'], 'host_organization_lineage_names': ['Centre National de la Recherche Scientifique'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': False, 'landing_page_url': 'https://hal.archives-ouvertes.fr/hal-01993372', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306402512', 'display_name': 'HAL (Le Centre pour la Communication Scientifique Directe)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I1294671590', 'host_organization_name': 'Centre National de la Recherche Scientifique', 'host_organization_lineage': ['https://openalex.org/I1294671590'], 'host_organization_lineage_names': ['Centre National de la Recherche Scientifique'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': False, 'landing_page_url': 'https://hal.archives-ouvertes.fr/hal-01482301', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306402512', 'display_name': 'HAL (Le Centre pour la Communication Scientifique Directe)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I1294671590', 'host_organization_name': 'Centre National de la Recherche Scientifique', 'host_organization_lineage': ['https://openalex.org/I1294671590'], 'host_organization_lineage_names': ['Centre National de la Recherche Scientifique'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': False, 'landing_page_url': 'https://hal.science/hal-01993372', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4306402512', 'display_name': 'HAL (Le Centre pour la Communication Scientifique Directe)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I1294671590', 'host_organization_name': 'Centre National de la Recherche Scientifique', 'host_organization_lineage': ['https://openalex.org/I1294671590'], 'host_organization_lineage_names': ['Centre National de la Recherche Scientifique'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/1310.6205', 'pdf_url': 'https://arxiv.org/pdf/1310.6205', 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, {'is_oa': True, 'landing_page_url': 'http://eprints.whiterose.ac.uk/89781/1/bullFreeFptFinal.pdf', 'pdf_url': 'http://eprints.whiterose.ac.uk/89781/1/bullFreeFptFinal.pdf', 'source': {'id': 'https://openalex.org/S4377196101', 'display_name': 'White Rose Research Online (University of Leeds)', 'issn_l': None, 'issn': None, 'is_oa': False, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I130828816', 'host_organization_name': 'University of Leeds', 'host_organization_lineage': ['https://openalex.org/I130828816'], 'host_organization_lineage_names': ['University of Leeds'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'acceptedVersion', 'is_accepted': True, 'is_published': False}, {'is_oa': False, 'landing_page_url': 'https://api.datacite.org/dois/10.48550/arxiv.1310.6205', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S4393179698', 'display_name': 'DataCite API', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I4210145204', 'host_organization_name': 'DataCite', 'host_organization_lineage': ['https://openalex.org/I4210145204'], 'host_organization_lineage_names': ['DataCite'], 'type': 'metadata'}, 'license': None, 'license_id': None, 'version': None}], 'best_oa_location': {'is_oa': True, 'landing_page_url': 'https://arxiv.org/abs/1310.6205', 'pdf_url': 'https://arxiv.org/pdf/1310.6205', 'source': {'id': 'https://openalex.org/S4306400194', 'display_name': 'arXiv (Cornell University)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I205783295', 'host_organization_name': 'Cornell University', 'host_organization_lineage': ['https://openalex.org/I205783295'], 'host_organization_lineage_names': ['Cornell University'], 'type': 'repository'}, 'license': None, 'license_id': None, 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}, 'sustainable_development_goals': [], 'grants': [{'funder': 'https://openalex.org/F4320334627', 'funder_display_name': 'Engineering and Physical Sciences Research Council', 'award_id': 'EP/K016423/1'}], 'datasets': [], 'versions': ['https://openalex.org/W1617257399', 'https://openalex.org/W3124564853'], 'referenced_works_count': 43, 'referenced_works': ['https://openalex.org/W133100469', 'https://openalex.org/W1539910521', 'https://openalex.org/W1615046544', 'https://openalex.org/W1789850899', 'https://openalex.org/W1868111879', 'https://openalex.org/W1971361630', 'https://openalex.org/W1971558924', 'https://openalex.org/W1972095231', 'https://openalex.org/W1973199140', 'https://openalex.org/W1979621874', 'https://openalex.org/W1991728994', 'https://openalex.org/W2002055996', 'https://openalex.org/W2003981436', 'https://openalex.org/W2008912593', 'https://openalex.org/W2019030165', 'https://openalex.org/W2068871408', 'https://openalex.org/W2077416162', 'https://openalex.org/W2088153883', 'https://openalex.org/W2089417393', 'https://openalex.org/W2096613302', 'https://openalex.org/W2100440346', 'https://openalex.org/W2107284348', 'https://openalex.org/W2117950870', 'https://openalex.org/W2158537726', 'https://openalex.org/W2179732776', 'https://openalex.org/W2183202562', 'https://openalex.org/W2187700168', 'https://openalex.org/W2248791588', 'https://openalex.org/W2296729072', 'https://openalex.org/W2340149117', 'https://openalex.org/W2486237862', 'https://openalex.org/W2615963353', 'https://openalex.org/W2620774572', 'https://openalex.org/W2763138650', 'https://openalex.org/W2913688336', 'https://openalex.org/W2952375877', 'https://openalex.org/W2977322974', 'https://openalex.org/W2988480584', 'https://openalex.org/W4231793127', 'https://openalex.org/W4234503811', 'https://openalex.org/W4292230561', 'https://openalex.org/W58553107', 'https://openalex.org/W968859509'], 'related_works': ['https://openalex.org/W4289672287', 'https://openalex.org/W300018836', 'https://openalex.org/W2972046864', 'https://openalex.org/W2054972273', 'https://openalex.org/W2029336174', 'https://openalex.org/W1995233739', 'https://openalex.org/W1973932399', 'https://openalex.org/W1968027460', 'https://openalex.org/W1608132493', 'https://openalex.org/W1492613353'], 'abstract_inverted_index': {'The': [0], 'maximum': [1, 147], 'stable': [2, 29, 122], 'set': [3, 30, 123], 'problem': [4, 60, 81], 'is': [5, 36, 47, 69, 136, 170], 'NP-hard,': [6], 'even': [7], 'when': [8, 34, 56], 'restricted': [9], 'to': [10, 48, 71, 108, 167, 175, 180], 'triangle-free': [11, 152], 'graphs.': [12], 'In': [13], 'particular,': [14], 'one': [15], 'cannot': [16], 'expect': [17], 'a': [18, 24, 28, 83, 99, 116, 133, 139, 160], 'polynomial': [19, 67, 84, 117], 'time': [20, 118], 'algorithm': [21, 55, 119], 'deciding': [22], 'if': [23, 101], 'bull-free': [25, 134, 164], 'graph': [26, 135], 'has': [27, 82], 'of': [31, 38, 52, 94, 115, 132, 141, 150], 'size': [32, 64, 85, 95], 'k,': [33], 'k': [35], 'part': [37], 'the': [39, 50, 59, 62, 89, 109, 113, 121, 129, 146], 'instance.': [40], 'Our': [41], 'main': [42], 'result': [43], 'in': [44, 106], 'this': [45, 74], 'paper': [46], 'show': [49, 77, 112], 'existence': [51, 114], 'an': [53], 'FPT': [54], 'we': [57, 102, 111], 'parameterize': [58], 'by': [61, 138], 'solution': [63], 'k.': [65], 'A': [66], 'kernel': [68], 'unlikely': [70], 'exist': [72], 'for': [73, 120, 163], 'problem.': [75, 124], 'We': [76, 125], 'however': [78], 'that': [79, 128], 'our': [80, 156, 181], 'Turing-kernel.': [86], 'More': [87], 'precisely,': [88], 'hard': [90], 'cases': [91], 'are': [92], 'instances': [93], '$${O}(k^5)$$': [96], '.': [97], 'As': [98], 'byproduct,': [100], 'forbid': [103], 'odd': [104], 'holes': [105], 'addition': [107], 'bull,': [110], 'also': [126], 'prove': [127], 'chromatic': [130, 148], 'number': [131, 144, 149], 'bounded': [137], 'function': [140], 'its': [142, 151], 'clique': [143], 'and': [145], 'induced': [153], 'subgraphs.': [154], 'All': [155], 'results': [157], 'rely': [158], 'on': [159], 'decomposition': [161], 'theorem': [162], 'graphs': [165], 'due': [166], 'Chudnovsky': [168], 'which': [169], 'modified': [171], 'here,': [172], 'allowing': [173], 'us': [174], 'provide': [176], 'extreme': [177], 'decompositions,': [178], 'adapted': [179], 'computational': [182], 'purpose.': [183]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W1617257399', 'counts_by_year': [{'year': 2021, 'cited_by_count': 1}, {'year': 2020, 'cited_by_count': 2}, {'year': 2019, 'cited_by_count': 2}, {'year': 2018, 'cited_by_count': 3}, {'year': 2017, 'cited_by_count': 3}, {'year': 2016, 'cited_by_count': 3}, {'year': 2015, 'cited_by_count': 3}, {'year': 2014, 'cited_by_count': 7}], 'updated_date': '2024-09-09T02:04:03.992805', 'created_date': '2016-06-24'}