A k-edge-coloring of a(n undirected) graph is an assignment of one of k possible colors to each of the edges of the graph such that different colors are assigned to any two adjacent (but different) edges. Given a weight function on colored edges of a graph G, a maximum-weight k-edge-coloring of G is a k-edge-coloring of a subgraph of G whose total weight of colored edges is maximum. The Maximum Weight Edge-Colored Subgraph asks, for a graph G, an integer k, and a weight function w for k-colored edges of G, to find a maximum-weight k-edge-colored subgraph of G. We propose a fixed-parameter tractable algorithm for the Maximum Weight Edge-Colored Subgraph problem with respect to two parameters: the branchwidth of the graph and the number k of colors. This result can be transferred to the treewidth.
Fixed-Parameter Tractability for Branchwidth of the Maximum-Weight Edge-Colored Subgraph Problem
Aloisio, Alessandro
2024-01-01
Abstract
A k-edge-coloring of a(n undirected) graph is an assignment of one of k possible colors to each of the edges of the graph such that different colors are assigned to any two adjacent (but different) edges. Given a weight function on colored edges of a graph G, a maximum-weight k-edge-coloring of G is a k-edge-coloring of a subgraph of G whose total weight of colored edges is maximum. The Maximum Weight Edge-Colored Subgraph asks, for a graph G, an integer k, and a weight function w for k-colored edges of G, to find a maximum-weight k-edge-colored subgraph of G. We propose a fixed-parameter tractable algorithm for the Maximum Weight Edge-Colored Subgraph problem with respect to two parameters: the branchwidth of the graph and the number k of colors. This result can be transferred to the treewidth.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
