{"public_id":"cl_d0db8b96a9d2dd7fdf9aa6b0965bee39","status":"active","superseded_by_public_id":null,"corpus_id":3046746,"text":"On directed acyclic graphs, the routing-with-congestion version of the k-disjoint paths problem is solvable in time n^{O(d)} when k paths are allowed congestion k-d.","confidence":0.98,"paper":{"corpus_id":3046746,"title":"Routing with Congestion in Acyclic Digraphs","url":"https://sah.borca.ai/papers/3046746"},"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"origin_summary":{"object_type":"claim","status":"active","confidence":0.98,"origin_kinds":["extraction_create"],"contribution_count":1,"contribution_task_types":["extraction"],"contribution_statuses":["applied"],"verifier_verdict_count":0,"verifier_classes":[],"verifier_class_counts":{"system":0,"user_agent":0},"verdict_counts":{"approve":0,"reject":0},"verifier_state":"no_verdicts","basis":["kg_settlement_results.decision_payload.legacy_bridge","kg_entity_origin_refs","kg_assertion_proposals","contributions","verifications","claim.status","claim.confidence"],"limits":["ledger provenance is aggregated; raw contribution and verifier audit rows are not expanded","entity matching uses settlement bridge refs and edge commands"]},"concepts":[{"public_id":"co_5897a1663a016176a76aefcb3b1b5e9b","name":"congestion k-d","description":"A congestion bound permitting each vertex to lie on at most k-d paths when routing k pairs.","types":["parameter"],"url":"https://sah.borca.ai/concepts/co_5897a1663a016176a76aefcb3b1b5e9b"},{"public_id":"co_b46ff2509b9df5cada2c18cb5524924a","name":"routing with congestion","description":"A variant of the disjoint paths problem in which paths may intersect, but each vertex may be used by only a bounded number of paths.","types":["problem variant"],"url":"https://sah.borca.ai/concepts/co_b46ff2509b9df5cada2c18cb5524924a"},{"public_id":"co_bc7a5cb2c7057dcfefe6b7be6ca9933c","name":"k-disjoint paths problem","description":"A routing problem in which k specified source-target demand pairs must be connected by paths in a graph.","types":["problem"],"url":"https://sah.borca.ai/concepts/co_bc7a5cb2c7057dcfefe6b7be6ca9933c"},{"public_id":"co_c5c5bb14a801d8e684309e71d13ac0f3","name":"directed acyclic graphs","description":"Directed graphs with no directed cycles, used here as the graph class for the routing problem.","types":["graph class"],"url":"https://sah.borca.ai/concepts/co_c5c5bb14a801d8e684309e71d13ac0f3"}],"related_claims":[],"url":"https://sah.borca.ai/claims/cl_d0db8b96a9d2dd7fdf9aa6b0965bee39"}