Graph coloring: a novel heuristic based on trailing path-properties, perspective and applications in structured networks

DOI10.1007/s00500-019-04278-8zbMath1436.05102OpenAlexW2801690537MaRDI QIDQ780266

Sankar Basu, Abhirup Bandyopadhyay, Amit Kumar Dhar

Publication date: 15 July 2020

Published in: Soft Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00500-019-04278-8

zbMATH Keywords

chromatic numbergraph partitioningprotein designmotif identifierNP to P

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Deterministic network models in operations research (90B10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Uses Software

• plfit
• gCol

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scale-free graph with preferential attachment and evolving internal vertex structure
• A novel parallel hybrid intelligence optimization algorithm for a function approximation problem
• An improved hybrid ant-local search algorithm for the partition graph coloring problem
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Hadwiger's conjecture is true for almost every graph
• A still better performance guarantee for approximate graph coloring
• Every planar map is four colorable. I: Discharging
• Total colouring regular bipartite graphs is NP-hard
• A dynamic survey of graph labeling
• A new \textsf{DSATUR}-based algorithm for exact vertex coloring
• On the complexity of the selective graph coloring problem in some special classes of graphs
• Conditional colorings of graphs
• A map colour theorem for the union of graphs
• Statistical mechanics of complex networks
• A Guide to Graph Colouring
• Power-Law Distributions in Empirical Data
• New methods to color the vertices of a graph
• On the Shannon capacity of a graph
• Reducibility among Combinatorial Problems
• Color-Induced Graph Colorings
• Euro-Par 2004 Parallel Processing
• Computational Complexity
• Collective dynamics of ‘small-world’ networks
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• On improving the edge-face coloring theorem