Call control with \(k\) rejections

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

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

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

68Q25: Analysis of algorithms and problem complexity

90B18: Communication networks in operations research

68R10: Graph theory (including graph drawing) in computer science

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

94A05: Communication theory

Related Items

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

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