Capacitated max-batching with interval graph compatibilities
DOI10.1016/J.TCS.2015.10.047zbMATH Open1333.05246OpenAlexW2186826687MaRDI QIDQ899311FDOQ899311
Authors: Tim Nonner 
Publication date: 28 December 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.10.047
Recommendations
- Capacitated max-batching with interval graph compatibilities
- Batch processing with interval graph compatibilities between tasks
- Parallel maximum matching algorithms in interval graphs
- Parallel algorithms for maximum matching in complements of interval graphs and related problems
- Scheduling a batch processing machine with bipartite compatibility graphs
- Online algorithms for scheduling on batch processing machines with interval graph compatibilities between jobs
- Scheduling on a batch processing machine with split compatibility graphs
- Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
- On the solution of a graph partitioning problem under capacity constraints
- Optimal parallel time bounds for the maximum clique problem on intervals
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Approximation schemes for covering and packing problems in image processing and VLSI
- Latency Constrained Aggregation in Sensor Networks
- Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime
- Batch processing with interval graph compatibilities between tasks
- Clique partitioning of interval graphs with submodular costs on the cliques
- Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
- Max-coloring and online coloring with bandwidths on interval graphs
- Scheduling unit tasks to minimize the number of idle periods
- On the max coloring problem
- Automata, Languages and Programming
- A quasi-PTAS for unsplittable flow on line graphs
- Restrictions of graph partition problems. I
- Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
- Dynamic scheduling on a single batch processing machine with split compatibility graphs
- Data Aggregation in Sensor Networks: Balancing Communication and Delay Costs
Cited In (2)
This page was built for publication: Capacitated max-batching with interval graph compatibilities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q899311)
