Complexity results for minimum sum edge coloring
type: Item
instance of: scholarly article
title: Complexity results for minimum sum edge coloring
zbMATH Open document ID: 1169.05382
author: Dániel Marx
published in: Discrete Applied Mathematics
publication date: 2009-06-30T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5572529
zbMATH Keywords: graph coloring
zbMATH Keywords: minimum sum coloring
zbMATH Keywords: minimum sum edge coloring
zbMATH Keywords: MSEC
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
full work available at URL: j.dam.2008.04.002
OpenAlex ID: W1974098993
cites work: Some APX-completeness results for cubic graphs
cites work: On chromatic sums and distributed resource allocation
cites work: Minimum Color Sum of Bipartite Graphs
cites work: Precoloring extension. I: Interval graphs
cites work: Q4291429
cites work: Q4699283
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Combinatorial Algorithms for Data Migration to Minimize Average Completion Time
cites work: Q4411283
cites work: Edge-chromatic sum of trees and bounded cyclicity graphs
cites work: Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
cites work: Q4838466
cites work: Precoloring Extension III: Classes of Perfect Graphs
cites work: The chromatic sum of a graph: history and recent developments
cites work: The membership problem in jump systems
cites work: Extending an edge-coloring
cites work: Approximation and Online Algorithms
cites work: NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
cites work: The complexity of chromatic strength and chromatic edge strength
cites work: On the sum coloring problem on interval graphs
cites work: The edge-disjoint paths problem is NP-complete for series-parallel graphs
cites work: On sum coloring of graphs
cites work: Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\cal NP$-Complete
cites work: Graph colorings with local constraints -- a survey
cites work: Algorithm for the cost edge-coloring of trees
DOI: 10.1016/J.DAM.2008.04.002
description: scientific article; zbMATH DE number 5572529