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

DOI10.1016/J.DISC.2004.08.042MaRDI QIDQ2484367zbMATH OpenOpenAlexFDO

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

Cell flippingClique numberDynamic programmingIndependent set numberMultiprocessor schedulingPermutation graphsStable set numberVLSI layout

Mathematics Subject Classification ID

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

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

• Algorithmic graph theory and perfect graphs
• Approximation algorithms for scheduling unrelated parallel machines
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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)