Publication:4659605

zbMath1061.05030MaRDI QIDQ4659605

Gerhard J. Woeginger, Sheng Gui Zhang, Hajo J. Broersma, Xue Liang Li

Publication date: 21 March 2005

zbMATH Keywords

edge-coloringapproximation algorithmsheterochromatic paths and cyclesmonochromatic paths and cycles

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15)

Related Items

Zeons, orthozeons, and graph colorings, Traveling salesman problems in temporal graphs, Binary constraint satisfaction problems defined by excluded topological minors, Sequence Hypergraphs, Complexity and approximation results on the shared transportation problem, An Introduction to Temporal Graphs: An Algorithmic Perspective, A note on heterochromatic \(C_4\) in edge-colored triangle-free graphs, On sufficient conditions for rainbow cycles in edge-colored graphs, On the hardness of labeled correlation clustering problem: a parameterized complexity view, The Complexity of Bottleneck Labeled Graph Problems, Approximation algorithms and hardness results for labeled connectivity problems, Sequence Hypergraphs: Paths, Flows, and Cuts, Approximation and hardness results for label cut and related problems, Rainbow cycles in edge-colored graphs, Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem, Unnamed Item, Improved approximation bounds for the minimum constraint removal problem, Labeled traveling salesman problems: complexity and approximation, The parameterized complexity of some minimum label problems, Minimum label \(s\)-\(t\) cut has large integrality gaps, On the minimum monochromatic or multicolored subgraph partition problems, The maximum labeled path problem, Algorithms and complexity results for labeled correlation clustering problem, The complexity of bottleneck labeled graph problems, A dynamic programming algorithm for solving the \(k\)-color shortest path problem, Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey, Color neighborhood union conditions for proper edge-pancyclicity of edge-colored complete graphs, The labeled perfect matching in bipartite graphs, An Introduction to Temporal Graphs: An Algorithmic Perspective^*, Approximate tradeoffs on weighted labeled matroids, Minimum Cell Connection in Line Segment Arrangements, Finding disjoint paths in networks with star shared risk link groups, An exact reduction technique for the k-colour shortest path problem, Note on rainbow triangles in edge-colored graphs, Rainbow \(C_4\)'s and directed \(C_4\)'s: the bipartite case study