Call control with \(k\) rejections

DOI10.1016/S0022-0000(03)00076-XzbMath1076.68016MaRDI QIDQ1877703

Alexander Hall, Stamatis Stefanakos, R. Sai Anand, Erlebach, Thomas

Publication date: 19 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

connection requests

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Communication networks in operations research (90B18) Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Communication theory (94A05)

Related Items

Parameterized Maximum Path Coloring, A top-down approach to search-trees: Improved algorithmics for 3-hitting set, Parameterized maximum path coloring, A fixed-parameter tractability result for multicommodity demand flow in trees, Approximation algorithms for the ring loading problem with penalty cost

Cites Work

• Primal-dual approximation algorithms for integral flow and multicut in trees
• An efficient fixed-parameter algorithm for 3-hitting set
• A partial k-arboretum of graphs with bounded treewidth
• A general method to speed up fixed-parameter-tractable algorithms
• On the \(k\)-coloring of intervals
• The Maximum Edge-Disjoint Paths Problem in Bidirected Trees
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item