Publication:4659605
From MaRDI portal
zbMath1061.05030MaRDI QIDQ4659605
Gerhard J. Woeginger, Sheng Gui Zhang, Hajo J. Broersma, Xue Liang Li
Publication date: 21 March 2005
edge-coloring; approximation algorithms; heterochromatic paths and cycles; monochromatic paths and cycles
68R10: Graph theory (including graph drawing) in computer science
05C38: Paths and cycles
05C15: Coloring of graphs and hypergraphs
Related Items
Unnamed Item, The complexity of bottleneck labeled graph problems, An Introduction to Temporal Graphs: An Algorithmic Perspective*, Sequence Hypergraphs: Paths, Flows, and Cuts, Rainbow \(C_4\)'s and directed \(C_4\)'s: the bipartite case study, Traveling salesman problems in temporal graphs, The maximum labeled path problem, Approximation and hardness results for label cut and related problems, On the hardness of labeled correlation clustering problem: a parameterized complexity view, Rainbow cycles in edge-colored graphs, Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey, The labeled perfect matching in bipartite graphs, Binary constraint satisfaction problems defined by excluded topological minors, Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem, A note on heterochromatic \(C_4\) in edge-colored triangle-free graphs, Labeled traveling salesman problems: complexity and approximation, The parameterized complexity of some minimum label problems, A dynamic programming algorithm for solving the \(k\)-color shortest path problem, Color neighborhood union conditions for proper edge-pancyclicity of edge-colored complete graphs, An exact reduction technique for the k-colour shortest path problem, Note on rainbow triangles in edge-colored graphs, Complexity and approximation results on the shared transportation problem, Improved approximation bounds for the minimum constraint removal problem, Minimum label \(s\)-\(t\) cut has large integrality gaps, Algorithms and complexity results for labeled correlation clustering problem, Approximate tradeoffs on weighted labeled matroids, Finding disjoint paths in networks with star shared risk link groups, Zeons, orthozeons, and graph colorings, On sufficient conditions for rainbow cycles in edge-colored graphs, Approximation algorithms and hardness results for labeled connectivity problems, On the minimum monochromatic or multicolored subgraph partition problems, Minimum Cell Connection in Line Segment Arrangements, Sequence Hypergraphs, An Introduction to Temporal Graphs: An Algorithmic Perspective, The Complexity of Bottleneck Labeled Graph Problems
