Publication Information

{'id': 'https://openalex.org/W2100699015', 'doi': 'https://doi.org/10.1109/sfcs.1996.548465', 'title': 'Single-source unsplittable flow', 'display_name': 'Single-source unsplittable flow', 'publication_year': 2002, 'publication_date': '2002-12-24', 'ids': {'openalex': 'https://openalex.org/W2100699015', 'doi': 'https://doi.org/10.1109/sfcs.1996.548465', 'mag': '2100699015'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1109/sfcs.1996.548465', '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/A5055710645', 'display_name': 'Jon Kleinberg', 'orcid': 'https://orcid.org/0000-0002-1929-2512'}, 'institutions': [{'id': 'https://openalex.org/I205783295', 'display_name': 'Cornell University', 'ror': 'https://ror.org/05bnh6r87', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I205783295']}, {'id': 'https://openalex.org/I4210085935', 'display_name': 'IBM Research - Almaden', 'ror': 'https://ror.org/005w8dd04', 'country_code': 'US', 'type': 'facility', 'lineage': ['https://openalex.org/I1341412227', 'https://openalex.org/I4210085935', 'https://openalex.org/I4210114115']}], 'countries': ['US'], 'is_corresponding': True, 'raw_author_name': 'J.M. Kleinberg', 'raw_affiliation_strings': ['Department of Computer Science, Cornell University, Ithaca, NY, USA', 'IBM Almaden Research Center, San Jose, CA, USA', 'MIT, Laboratory of Computer Science, Cambridge, MA, USA'], 'affiliations': [{'raw_affiliation_string': 'Department of Computer Science, Cornell University, Ithaca, NY, USA', 'institution_ids': ['https://openalex.org/I205783295']}, {'raw_affiliation_string': 'IBM Almaden Research Center, San Jose, CA, USA', 'institution_ids': ['https://openalex.org/I4210085935']}, {'raw_affiliation_string': 'MIT, Laboratory of Computer Science, Cambridge, MA, USA', 'institution_ids': []}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 2, 'corresponding_author_ids': ['https://openalex.org/A5055710645'], 'corresponding_institution_ids': ['https://openalex.org/I205783295', 'https://openalex.org/I4210085935'], 'apc_list': None, 'apc_paid': None, 'fwci': 8.024, 'has_fulltext': True, 'fulltext_origin': 'ngrams', 'cited_by_count': 154, 'citation_normalized_percentile': {'value': 0.99485, 'is_in_top_1_percent': True, 'is_in_top_10_percent': True}, 'cited_by_percentile_year': {'min': 97, 'max': 98}, 'biblio': {'volume': None, 'issue': None, 'first_page': None, 'last_page': None}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T12288', 'display_name': 'Optimization and Search Problems', 'score': 0.9997, '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'}}, 'topics': [{'id': 'https://openalex.org/T12288', 'display_name': 'Optimization and Search Problems', 'score': 0.9997, '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/T10551', 'display_name': 'Scheduling and Optimization Algorithms', 'score': 0.999, 'subfield': {'id': 'https://openalex.org/subfields/2209', 'display_name': 'Industrial and Manufacturing Engineering'}, 'field': {'id': 'https://openalex.org/fields/22', 'display_name': 'Engineering'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T10567', 'display_name': 'Vehicle Routing Optimization Methods', 'score': 0.9978, 'subfield': {'id': 'https://openalex.org/subfields/2209', 'display_name': 'Industrial and Manufacturing Engineering'}, 'field': {'id': 'https://openalex.org/fields/22', 'display_name': 'Engineering'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/rounding', 'display_name': 'Rounding', 'score': 0.73035395}, {'id': 'https://openalex.org/keywords/randomized-rounding', 'display_name': 'Randomized rounding', 'score': 0.55751055}, {'id': 'https://openalex.org/keywords/disjoint-sets', 'display_name': 'Disjoint sets', 'score': 0.5400184}, {'id': 'https://openalex.org/keywords/constant', 'display_name': 'Constant (computer programming)', 'score': 0.42052126}, {'id': 'https://openalex.org/keywords/multi-commodity-flow-problem', 'display_name': 'Multi-commodity flow problem', 'score': 0.419556}], 'concepts': [{'id': 'https://openalex.org/C136625980', 'wikidata': 'https://www.wikidata.org/wiki/Q663208', 'display_name': 'Rounding', 'level': 2, 'score': 0.73035395}, {'id': 'https://openalex.org/C148764684', 'wikidata': 'https://www.wikidata.org/wiki/Q621751', 'display_name': 'Approximation algorithm', 'level': 2, 'score': 0.6576827}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.575122}, {'id': 'https://openalex.org/C80899671', 'wikidata': 'https://www.wikidata.org/wiki/Q1304193', 'display_name': 'Vertex (graph theory)', 'level': 3, 'score': 0.57494974}, {'id': 'https://openalex.org/C34388435', 'wikidata': 'https://www.wikidata.org/wiki/Q2267362', 'display_name': 'Bounded function', 'level': 2, 'score': 0.56185746}, {'id': 'https://openalex.org/C32029473', 'wikidata': 'https://www.wikidata.org/wiki/Q7292010', 'display_name': 'Randomized rounding', 'level': 3, 'score': 0.55751055}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.5477828}, {'id': 'https://openalex.org/C45340560', 'wikidata': 'https://www.wikidata.org/wiki/Q215382', 'display_name': 'Disjoint sets', 'level': 2, 'score': 0.5400184}, {'id': 'https://openalex.org/C177148314', 'wikidata': 'https://www.wikidata.org/wiki/Q170084', 'display_name': 'Generalization', 'level': 2, 'score': 0.5014391}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.50089455}, {'id': 'https://openalex.org/C146380142', 'wikidata': 'https://www.wikidata.org/wiki/Q1137726', 'display_name': 'Directed graph', 'level': 2, 'score': 0.48575643}, {'id': 'https://openalex.org/C2777735758', 'wikidata': 'https://www.wikidata.org/wiki/Q817765', 'display_name': 'Path (computing)', 'level': 2, 'score': 0.43671143}, {'id': 'https://openalex.org/C2777027219', 'wikidata': 'https://www.wikidata.org/wiki/Q1284190', 'display_name': 'Constant (computer programming)', 'level': 2, 'score': 0.42052126}, {'id': 'https://openalex.org/C170334043', 'wikidata': 'https://www.wikidata.org/wiki/Q6934437', 'display_name': 'Multi-commodity flow problem', 'level': 3, 'score': 0.419556}, {'id': 'https://openalex.org/C132525143', 'wikidata': 'https://www.wikidata.org/wiki/Q141488', 'display_name': 'Graph', 'level': 2, 'score': 0.39}, {'id': 'https://openalex.org/C114809511', 'wikidata': 'https://www.wikidata.org/wiki/Q1412924', 'display_name': 'Flow network', 'level': 2, 'score': 0.38585454}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.29389924}, {'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/C199360897', 'wikidata': 'https://www.wikidata.org/wiki/Q9143', 'display_name': 'Programming language', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C111919701', 'wikidata': 'https://www.wikidata.org/wiki/Q9135', 'display_name': 'Operating system', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1109/sfcs.1996.548465', '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': 21, 'referenced_works': ['https://openalex.org/W100926944', 'https://openalex.org/W1563039933', 'https://openalex.org/W156931726', 'https://openalex.org/W1990361925', 'https://openalex.org/W2012959686', 'https://openalex.org/W2022191808', 'https://openalex.org/W2023176678', 'https://openalex.org/W2027920448', 'https://openalex.org/W2046825771', 'https://openalex.org/W2058264792', 'https://openalex.org/W2061756358', 'https://openalex.org/W2062948942', 'https://openalex.org/W2064779029', 'https://openalex.org/W2093979815', 'https://openalex.org/W2103389589', 'https://openalex.org/W2114218179', 'https://openalex.org/W2121839513', 'https://openalex.org/W2139739478', 'https://openalex.org/W3011766368', 'https://openalex.org/W4213060883', 'https://openalex.org/W976211528'], 'related_works': ['https://openalex.org/W99223781', 'https://openalex.org/W4308670308', 'https://openalex.org/W4287779968', 'https://openalex.org/W2952768013', 'https://openalex.org/W2951032362', 'https://openalex.org/W2117676893', 'https://openalex.org/W2100699015', 'https://openalex.org/W2036125948', 'https://openalex.org/W1601007368', 'https://openalex.org/W1556533447'], 'abstract_inverted_index': {'The': [0, 109, 154, 178], 'max-flow': [1], 'min-cut': [2], 'theorem': [3, 18, 23], 'of': [4, 65, 101, 131, 139, 157, 169, 180, 186, 199, 211, 227, 239, 244, 247], 'Ford': [5], 'and': [6, 44, 81, 97, 175, 219, 229, 251], 'Fulkerson': [7], 'is': [8, 111], 'based': [9], 'on': [10, 19], 'an': [11, 213], 'even': [12], 'more': [13], 'foundational': [14], 'result,': [15], 'namely': [16], "Menger's": [17, 22], 'graph': [20, 37], 'connectivity': [21], 'provides': [24, 231], 'a': [25, 36, 40, 61, 79, 92, 104, 118, 184, 232, 245], 'good': [26], 'characterization': [27], 'for': [28, 57, 123, 164, 189, 197, 220], 'the': [29, 71, 128, 134, 150, 200, 216, 221, 223, 242, 260], 'following': [30], 'single-source': [31, 72, 261], 'disjoint': [32], 'paths': [33, 56, 132], 'problem:': [34], 'given': [35, 78], 'G,': [38], 'with': [39], 'source': [41, 80], 'vertex': [42], 's': [43], 'terminals': [45, 82], 't/sub': [46, 89], '1/,...,t/sub': [47], 'k/,': [48], 'decide': [49, 113], 'whether': [50, 114], 'there': [51, 205], 'exist': [52], 'edge-disjoint': [53], 's-t/sub': [54, 120], 'i/': [55, 90, 121], 'i=1,...,k.': [58], 'We': [59, 76], 'consider': [60], 'natural,': [62], 'NP-hard': [63, 248], 'generalization': [64], 'this': [66, 158, 170], 'problem,': [67, 171], 'which': [68], 'we': [69, 203], 'call': [70], 'unsplittable': [73, 262], 'flow': [74, 195, 263], 'problem.': [75, 264], 'are': [77, 160, 237], 'as': [83], 'before;': [84], 'but': [85], 'now': [86], 'each': [87, 98, 124], 'terminal': [88], 'has': [91, 103], 'demand': [93, 140], 'p/sub': [94], 'i//spl': [95], 'les/1,': [96], 'edge': [99, 144], 'e': [100, 145], 'G': [102], 'capacity': [105, 135, 151], 'c/sub': [106, 152], 'e//spl': [107], 'ges/1.': [108], 'problem': [110], 'to': [112, 193, 259], 'one': [115], 'can': [116, 256], 'choose': [117], 'single': [119], 'path': [122], 'i,': [125], 'so': [126], 'that': [127, 255], 'resulting': [129], 'set': [130], 'respects': [133], 'constraints-the': [136], 'total': [137], 'amount': [138], 'routed': [141], 'across': [142], 'any': [143], 'must': [146], 'be': [147, 257], 'bounded': [148], 'by': [149], 'e/.': [153], 'main': [155], 'results': [156], 'paper': [159], 'constant-factor': [161], 'approximation': [162, 214], 'algorithms': [163, 182], 'three': [165, 201], 'natural': [166], 'optimization': [167], 'versions': [168], 'in': [172, 215], 'arbitrary': [173], 'directed': [174], 'undirected': [176], 'graphs.': [177], 'development': [179], 'these': [181], 'requires': [183], 'number': [185], 'new': [187], 'techniques': [188, 209, 236], 'rounding': [190, 225], 'fractional': [191], 'solutions': [192], 'network': [194], 'problems;': [196], 'two': [198], 'problems': [202, 254], 'consider,': [204], 'were': [206], 'no': [207], 'previous': [208], 'capable': [210], 'providing': [212], 'general': [217], 'case,': [218], 'third,': [222], 'randomized': [224], 'algorithm': [226], 'Raghavan': [228], 'Thompson': [230], 'logarithmic': [233], 'approximation.': [234], 'Our': [235], 'also': [238], 'interest': [240], 'from': [241], 'perspective': [243], 'family': [246], 'load': [249], 'balancing': [250], 'machine': [252], 'scheduling': [253], 'reduced': [258]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2100699015', 'counts_by_year': [{'year': 2024, 'cited_by_count': 1}, {'year': 2023, 'cited_by_count': 2}, {'year': 2022, 'cited_by_count': 2}, {'year': 2021, 'cited_by_count': 2}, {'year': 2020, 'cited_by_count': 3}, {'year': 2018, 'cited_by_count': 2}, {'year': 2017, 'cited_by_count': 6}, {'year': 2016, 'cited_by_count': 7}, {'year': 2015, 'cited_by_count': 6}, {'year': 2014, 'cited_by_count': 8}, {'year': 2013, 'cited_by_count': 7}, {'year': 2012, 'cited_by_count': 4}], 'updated_date': '2024-12-14T00:40:11.986089', 'created_date': '2016-06-24'}