New methods to color the vertices of a graph
From MaRDI portal
Publication:4175306
DOI10.1145/359094.359101zbMath0394.05022OpenAlexW2167036627WikidataQ56269084 ScholiaQ56269084MaRDI QIDQ4175306
Publication date: 1979
Published in: Communications of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/359094.359101
SchedulingBipartite GraphsGraph ColoringVertex ColoringBalancingComparison Of MethodsFind Maximal Cliques in General GraphsGraph StructureNp CompleteRandall-Brown Algorithm
Coloring of graphs and hypergraphs (05C15) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items
Routing and wavelength assignment by partition colouring, Chromatic scheduling and frequency assignment, An exact algorithm for the maximum stable set problem, Hybrid evolutionary search for the minimum sum coloring problem of graphs, Hard-to-color graphs for connected sequential colorings, A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations, Graph colouring approaches for a satellite range scheduling problem, A survey of search methodologies and automated system development for examination timetabling, A multi-objective evolutionary algorithm for examination timetabling, Interval branch-and-bound algorithms for optimization and constraint satisfaction: a survey and prospects, Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: A survey of the state-of-the-art, Improving paper spread in examination timetables using integer programming, Fast heuristics for the frequency channel assignment problem in multi-hop wireless networks, Symmetry breaking constraints for value symmetries in constraint satisfaction, The impact of search heuristics on heavy-tailed behaviour, Lower bounding techniques for DSATUR-based branch and bound, Reducing graph coloring to clique search, New secure partial encryption method for medical images using graph coloring problem, Towards objective measures of algorithm performance across instance space, An exact algorithm with learning for the graph coloring problem, A DSATUR-based algorithm for the equitable coloring problem, Online algorithms for the maximum \(k\)-colorable subgraph problem, A cellular memetic algorithm for the examination timetabling problem, Compromise ratio with weighting functions in a tabu search multi-criteria approach to examination timetabling, Spectrum graph coloring and applications to Wi-Fi channel assignment, Frequency assignment in a SDMA satellite communication system with beam decentring feature, Strong valid inequalities for Boolean logical pattern generation, Interleaving solving and elicitation of constraint satisfaction problems based on expected cost, Parallel graph component labelling with GPUs and CUDA, Algorithms for the maximum \(k\)-club problem in graphs, A multiobjective framework for heavily constrained examination timetabling problems, Discovering implied constraints in precedence graphs with alternatives, Planning of high school examinations in Denmark, Average-case complexity of backtrack search for coloring sparse random graphs, Graph multi-coloring for a job scheduling application, Exploring the role of graph spectra in graph coloring algorithm performance, Genetic tabu search for robust fixed channel assignment under dynamic traffic data, On biconnected and fragile subgraphs of low diameter, Information-theoretic approaches to branching in search, An exact approach for the vertex coloring problem, A variable neighborhood search for graph coloring., Combinatorial algorithms for the maximum \(k\)-plex problem, Constraint-based very large-scale neighborhood search, Approximate derivative computations for the gradient-based optimization methods in the local gradual deformation for history matching, On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs, Chromatic optimisation: Limitations, objectives, uses, references, Coloring certain proximity graphs, Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz, On the chromatic number of \(\mathbb R^4\), The cook-book approach to the differential equation method, A cooperative search method for the \(k\)-coloring problem, Memetic techniques for examination timetabling, A flow based pruning scheme for enumerative equitable coloring algorithms, Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths, Heuristic for rapidly four-coloring large planar graphs, COSINE: A new graph coloring algorithm, A sequential elimination algorithm for computing bounds on the clique number of a graph, Weighted graphs and university course timetabling, Enhanced multiple-point statistical simulation with backtracking, forward checking and conflict-directed backjumping, Co-2-plex vertex partitions, Decomposing clique search problems into smaller instances based on node and edge colorings, Nested annealing: A provable improvement to simulated annealing, A logic approach to the resolution of constraints in timetabling, Solving vertex coloring problems as maximum weight stable set problems, A branch and price algorithm to solve the integrated production planning and scheduling in bulk ports, Enumeration of the partitions with minimum diameter, Hybrid evolutionary algorithm for the b-chromatic number, Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems, Formation control using range-only measurements, A wide-ranging computational comparison of high-performance graph colouring algorithms, A harmony search algorithm for university course timetabling, Linear combinations of heuristics for examination timetabling, An improved multi-staged algorithmic process for~the~solution of the examination timetabling problem, A time-dependent metaheuristic algorithm for post enrolment-based course timetabling, On the application of graph colouring techniques in round-robin sports scheduling, Improving the extraction and expansion method for large graph coloring, Some experiments with simulated annealing for coloring graphs, A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing, An algorithm for finding a maximum clique in a graph, An introduction to timetabling, Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems, Combinatorial optimization in system configuration design, Three new upper bounds on the chromatic number, Graph coloring by multiagent fusion search, Models and heuristic algorithms for a weighted vertex coloring problem, Backtracking algorithms for disjunctions of temporal constraints, Connected greedy coloring of \(H\)-free graphs, A search space ``cartography for guiding graph coloring heuristics, On a parallel genetic-tabu search based algorithm for solving the graph colouring problem, Graph coloring: a novel heuristic based on trailing path-properties, perspective and applications in structured networks, A memetic algorithm for graph coloring, Reasoning from last conflict(s) in constraint programming, AND/OR branch-and-bound search for combinatorial optimization in graphical models, Recent research directions in automated timetabling, Worst case analysis of a graph coloring algorithm, The clique-partitioning problem, Finding maximum cliques in arbitrary and in special graphs, A fast algorithm for the maximum weight clique problem, The maximum clique problem, Numerical experiences with graph coloring algorithms, A Novel Approach for Detecting Relationships in Social Networks Using Cellular Automata Based Graph Coloring, Graph Coloring Lower Bounds from Decision Diagrams, On the use of some known methods for \(T\)-colorings of graphs, A branch and price algorithm for list coloring problem, Eigen-stratified models, A review on algorithms for maximum clique problems, Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm, Sampling Strategies for Fast Updating of Gaussian Markov Random Fields, Iterative coloring extension of a maximum clique, Adaptive tabu search for course timetabling, Variable ordering for decision diagrams: a portfolio approach, Homogeneous grouping of non-prime steel products for online auctions: a case study, Simple decentralized graph coloring, On Monte Carlo tree search for weighted vertex coloring, Adaptive large neighborhood search for the curriculum-based course timetabling problem, Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring, An exact algorithm for parallel machine scheduling with conflicts, Genetic and hybrid algorithms for graph coloring, A tabu search algorithm with controlled randomization for constructing feasible university course timetables, Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs, Complexity of Coloring Random Graphs, An exact algorithm for the edge coloring by total labeling problem, Graph Coloring Using Eigenvalue Decomposition, A comparison of integer programming models for the partial directed weighted improper coloring problem, Vertex coloring of a graph for memory constrained scenarios, Weighted improper colouring, Very Large-Scale Neighborhood Search: Overview and Case Studies on Coloring Problems, Graph theoretic algorithm for automatic operation sequencing for progressive die design, Models and methods for frequency assignment with cumulative interference constraints, Matrix-Free Convex Optimization Modeling, Symmetry-breaking inequalities for ILP with structured sub-symmetry, A new vertex coloring heuristic and corresponding chromatic number, Efficient circuits for permuting and mapping packed values across leveled homomorphic ciphertexts, Scheduling on uniform machines with a conflict graph: complexity and resolution, Maximum-weight stable sets and safe lower bounds for graph coloring, Local optimization of colorings of graphs, A graph-based hyper-heuristic for educational timetabling problems, A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows, Algorithms for a shared resource scheduling problem in which some level of conflict is tolerable, A survey of graph coloring - its types, methods and applications, Constraint and Satisfiability Reasoning for Graph Coloring, Multi-coloring and job-scheduling with assignment and incompatibility costs, The general \(\alpha \)-decomposition problem of fuzzy relations, A graph coloring heuristic using partial solutions and a reactive tabu scheme, Exploiting incomplete information to manage multiprocessor tasks with variable arrival rates, Investigating Ahuja-Orlin's large neighbourhood search approach for examination timetabling, Fast tensor product Schwarz smoothers for high-order discontinuous Galerkin methods, Safe Lower Bounds for Graph Coloring, Generalised graph colouring by a hybrid of local search and constraint programming, A cutting plane algorithm for graph coloring, A semidefinite programming-based heuristic for graph coloring, An ant-based algorithm for coloring graphs, Coloring graphs by iterated local search traversing feasible and infeasible solutions, Constructive generation of very hard 3-colorability instances, An adaptive memory algorithm for the \(k\)-coloring problem, Graph coloring in the estimation of sparse derivative matrices: Instances and applications, Unnamed Item, An improved ant colony optimisation heuristic for graph colouring, Solving the minimum-weighted coloring problem, A branch and bound algorithm for the maximum clique problem, An evolutionary approach for bandwidth multicoloring problems, Embedding a novel objective function in a two-phased local search for robust vertex coloring, Managing the tabu list length using a fuzzy inference system: an application to examination timetabling, Cliques with maximum/minimum edge neighborhood and neighborhood density, A new \textsf{DSATUR}-based algorithm for exact vertex coloring, Joint routing and wavelength assignment in wavelength division multiplexing networks for permanent and reliable paths, Heuristics and lower bounds for the bin packing problem with conflicts, Solving the maximum edge-weight clique problem in sparse graphs with compact formulations, An exact method for graph coloring, A survey of local search methods for graph coloring, A branch-and-cut algorithm for graph coloring, Algorithm portfolios, On the chromatic number of graphs, Constraint solving for proof planning, Accelerating backtrack search with a best-first-search strategy, Some sequential graph colouring algorithms, Models and solution techniques for frequency assignment problems, A NEW APPROACH TO THE VERTEX COLORING PROBLEM, Parallel Immune System for Graph Coloring, Almost all graphs with average degree 4 are 3-colorable, On the recursive largest first algorithm for graph colouring, Privacy-preserving data splitting: a combinatorial approach, EPCOT: An efficient procedure for coloring optimally with Tabu Search, An Extended Comparison of the Best Known Algorithms for Finding the Unweighted Maximum Clique, Distance-Based Clique Relaxations in Networks: s-Clique and s-Club, An incremental search heuristic for coloring vertices of a graph, Simulating Markov Random Fields With a Conclique-Based Gibbs Sampler, Three algorithms for graph locally harmonious colouring, CsegGraph: a graph colouring instance generator, Graphs and Algorithms in Communication Networks on Seven League Boots, Estimating clique size by coloring the nodes of auxiliary graphs, Pickup and delivery problem with incompatibility constraints, The variational quantum eigensolver: a review of methods and best practices, An information-based neural approach to generic constraint satisfaction., Optimal direct determination of sparse Jacobian matrices, Coloring Meyniel graphs in linear time, Bi-Directional Determination of Sparse Jacobian Matrices: Approaches and Algorithms, AN EXTRACTION AND EXPANSION APPROACH FOR GRAPH COLORING, Graph coloring with decision diagrams
