Approximating maximum edge coloring in multigraphs

DOI10.1007/3-540-45753-4_11MaRDI QIDQ4411281zbMATH OpenFDO

Authors Eran Ofek, Udi Wieder, Uriel Feige

Publication date 7 July 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2462/24620108.htm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Approximation Algorithms for Maximum Edge Coloring Problem
• Approximation algorithm for maximum edge coloring
• Approximating the max-edge-coloring problem
• An asymptotic approximation scheme for multigraph edge coloring
• A better than “best possible” algorithm to edge color multigraphs

Cited in

(35)

• Approximation algorithm for maximum edge coloring
• Approximating maximum edge 2-coloring in simple graphs via local improvement
• Approximating the maximum 3-edge-colorable subgraph problem
• Minimum multiplicity edge coloring via orientation
• Online edge coloring of paths and trees with a fixed number of colors
• Parameterized complexity of \textsc{maximum edge colorable subgraph}
• Parameterized complexity of maximum edge colorable subgraph
• Characterization of saturated graphs related to pairs of disjoint matchings
• On packing and coloring hyperedges in a cycle
• Packing \([1, \Delta ]\)-factors in graphs of small degree
• Using the minimum maximum flow degree to approximate the flow coloring problem
• Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
• Parameterized and approximation algorithms for finding two disjoint matchings
• Approximation and Hardness Results for the Maximum Edge q-coloring Problem
• Approximation and hardness results for the maximum edge q-coloring problem
• Approximating Maximum Edge 2-Coloring in Simple Graphs Via Local Improvement
• On the Maximum Edge Coloring Problem
• Optimal edge coloring of large graphs
• Some maximum multigraphs and adge/vertex distance colourings
• An asymptotic approximation scheme for multigraph edge coloring
• Edge Colouring with Delays
• Approximation Algorithms for Maximum Edge Coloring Problem
• Computing and Combinatorics
• Efficiently list‐edge coloring multigraphs asymptotically optimally
• Diverse Pairs of Matchings
• Approximating maximum edge 2-coloring in simple graphs
• Pairs of disjoint matchings and related classes of graphs
• Diverse pairs of matchings
• The maximum 2-edge-colorable subgraph problem and its fixed-parameter tractability
• A backtracking algorithm for solving the nearly equitable strong edge-coloring problem on transportation network
• Semi-streaming algorithms for weighted k-disjoint matchings
• Edge coloring of multigraphs with very high multiplicities
• \((p,k)\)-coloring problems in line graphs
• An improved approximation algorithm for maximum edge 2-coloring in simple graphs
• Approximating the maximum 2- and 3-edge-colorable subgraph problems

This page was built for publication: Approximating maximum edge coloring in multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4411281)