We describe space-efficient algorithms for two problems on undirected multigraphs: Euler partition (partitioning the edges into a minimum number of trails); and bipartite edge coloring (coloring the edges of a bipartite multigraph with the minimum number of colors). Let n, m and Δ ≥ 1 be the numbers of vertices and of edges and the maximum degree, respectively, of the input multigraph. For Euler partition we reduce the amount of working memory needed by a logarithmic factor, to O(n+m) bits, while preserving a running time of O(n+m). For bipartite edge coloring, still using O(n+m) bits of working memory, we achieve a running time of O(n+m min{Δ, log Δ(log~* Δ + (log m log Δ)/Δ)}). This is O(m log Δ log~* Δ) if m = Ω(n log n log log n/log~*n), to be compared with O(m log Δ) for the fastest known algorithm.
展开▼
机译：我们描述了空间高效的算法，有关无向多角形的两个问题：欧拉分区（将边缘划分为最小迹线）;和二分的边缘着色（用最小数量的颜色着色二分层多角形的边缘）。让N，M和Δ≥1是输入多密片的顶点和边缘的数量和最大程度。对于欧拉分区，我们将对数因子所需的工作存储器减少到O（n + m）位，同时保留O（n + m）的运行时间。对于二分的边缘着色，仍然使用O（n + m）的工作存储器，我们实现了O的运行时间（n + m min {δ，logδ（log〜*δ+（log m logδ）/Δ） }）。如果m =ω（n log n log log n / log〜* n），则为O（m logΔlog〜*Δ），以便与最快已知的算法与O（m logδ）进行比较。
展开▼
