On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems

DOI10.1016/J.DISC.2004.08.042zbMATH Open1079.68073OpenAlexW2085311936MaRDI QIDQ2484367FDOQ2484367

Authors Martin Charles Golumbic, Elad Verbin, Haim Kaplan 

Publication date 1 August 2005

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2004.08.042

zbMATH Keywords

VLSI layoutDynamic programmingPermutation graphsMultiprocessor schedulingClique numberCell flippingIndependent set numberStable set number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• scientific article; zbMATH DE number 3904502
• Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Parallel algorithms for permutation graphs
• Circular permutation graph family with applications

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• Approximation algorithms for scheduling unrelated parallel machines
• On a scheduling problem where a job can be executed only by a limited number of processors
• On computing the length of longest increasing subsequences
• Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization
• Scheduling unit-time jobs on processors with different capabilities
• Some Matching Problems for Bipartite Graphs
• The Multiple-Choice Knapsack Problem

This page was built for publication: On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2484367)