Mutual exclusion scheduling with interval graphs or related classes. I
From MaRDI portal
Publication:1003752
DOI10.1016/J.DAM.2008.04.016zbMATH Open1155.90381OpenAlexW2043493954MaRDI QIDQ1003752FDOQ1003752
Publication date: 4 March 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.04.016
Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Reducibility among Combinatorial Problems
- Graph Classes: A Survey
- Efficient algorithms for interval graphs and circular-arc graphs
- The Complexity of Coloring Circular Arcs and Chords
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Simple linear time recognition of unit interval graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Interval graphs and interval orders
- Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
- The mutual exclusion scheduling problem for permutation and comparability graphs.
- Maximum matching in a convex bipartite graph
- Restricted coloring models for timetabling
- Mutual exclusion scheduling
- A linear time algorithm for maximum matchings in convex, bipartite graphs
- Scheduling with constrained processor allocation for interval orders
- Chromatic optimisation: Limitations, objectives, uses, references
- NP-completeness of graph decomposition problems
- Bounded vertex coloring of trees
- Restrictions of graph partition problems. I
- A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
- An \(0(n^{1.5})\) algorithm to color proper circular arcs
- Mutual exclusion scheduling with interval graphs or related classes: complexity and algorithms
- Parallel algorithms for maximum matching in complements of interval graphs and related problems
- Matching and multidimensional matching in chordal and strongly chordal graphs
- Finding a Maximum Clique in a Set of Proper Circular Arcs in Time O(n) with Applications
- Mathematical Foundations of Computer Science 2004
- Maximum skew-symmetric flows
Cited In (17)
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- Scheduling with machine conflicts
- Open shop scheduling problems with conflict graphs
- Scheduling: agreement graph vs resource constraints
- Clique partitioning with value-monotone submodular cost
- Flow shop scheduling problem with conflict graphs
- On maximizing the profit of a satellite launcher: selecting and scheduling tasks with time windows and setups
- Two-machine open shop problem with agreement graph
- An exact algorithm for parallel machine scheduling with conflicts
- Periodic assignment and graph colouring
- Title not available (Why is that?)
- Scheduling identical jobs on uniform machines with a conflict graph
- Scheduling on uniform machines with a conflict graph: complexity and resolution
- New results in two identical machines scheduling with agreement graphs
- The mutual exclusion scheduling problem for permutation and comparability graphs.
- Scheduling jobs on identical machines with agreement graph
- On partitioning interval graphs into proper interval subgraphs and related problems
This page was built for publication: Mutual exclusion scheduling with interval graphs or related classes. I
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1003752)
