Restrictions of graph partition problems. I

DOI10.1016/0304-3975(95)00057-4zbMath0873.68158DBLPjournals/tcs/BodlaenderJ95OpenAlexW2049181186WikidataQ59567991 ScholiaQ59567991MaRDI QIDQ672380

Klaus Jansen, Hans L. Bodlaender

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00057-4

zbMATH Keywords

job-assignment problem

Mathematics Subject Classification ID

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

Related Items (33)

Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph ⋮ Scheduling: agreement graph vs resource constraints ⋮ On partitioning interval graphs into proper interval subgraphs and related problems ⋮ Scheduling with conflicts: Online and offline algorithms ⋮ Approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms ⋮ Mutual exclusion scheduling ⋮ On the thinness and proper thinness of a graph ⋮ New results in two identical machines scheduling with agreement graphs ⋮ Weighted and locally bounded list-colorings in split graphs, cographs, and partial \(k\)-trees ⋮ Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints ⋮ Window-based greedy contention management for transactional memory: theory and practice ⋮ Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization ⋮ Capacitated max-batching with interval graph compatibilities ⋮ Scheduling with machine conflicts ⋮ A competitive analysis for balanced transactional memory workloads ⋮ Scheduling on uniform machines with a conflict graph: complexity and resolution ⋮ An improved algorithm for parallel machine scheduling under additional resource constraints ⋮ Tree partitioning under constraints. -- Clustering for vehicle routing problems ⋮ Bounded max-colorings of graphs ⋮ Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem ⋮ Batch processing with interval graph compatibilities between tasks ⋮ Mutual exclusion scheduling with interval graphs or related classes. II ⋮ Scheduling jobs on identical machines with agreement graph ⋮ Scheduling identical jobs on uniform machines with a conflict graph ⋮ Some approximation algorithms for the clique partition problem in weighted interval graphs ⋮ Mutual exclusion scheduling with interval graphs or related classes. I ⋮ “Rent-or-Buy” Scheduling and Cost Coloring Problems ⋮ Locally boundedk-colorings of trees ⋮ A hybrid metaheuristic for the two-dimensional strip packing problem ⋮ Asynchronous Coordination Under Preferences and Constraints ⋮ Clique partitioning with value-monotone submodular cost ⋮ Equitable colorings of bounded treewidth graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Processor optimization for flow graphs
• On a property of the class of n-colorable graphs
• A Linear Recognition Algorithm for Cographs
• The NP-completeness column: an ongoing guide
• Scheduling Interval-Ordered Tasks
• Efficient algorithms for interval graphs and circular-arc graphs

This page was built for publication: Restrictions of graph partition problems. I