Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
From MaRDI portal
Publication:873646
DOI10.1007/s004930170002zbMath1107.05305OpenAlexW1971663478WikidataQ56390636 ScholiaQ56390636MaRDI QIDQ873646
Kirstin Ost, Stefan Schirra, Richard John Cole
Publication date: 29 March 2007
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s004930170002
Related Items
Tight bounds on maximal and maximum matchings, Space-Efficient Euler Partition and Bipartite Edge Coloring, A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job, Space-efficient Euler partition and bipartite edge coloring, Approximate constrained bipartite edge coloring, Graph optimization approaches for minimal rerouting in symmetric three stage Clos networks, Trees, paths, stars, caterpillars and spiders, Distributed edge coloration for bipartite networks, An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times, A self-stabilizing \((\Delta +4)\)-edge-coloring algorithm for planar graphs in anonymous uniform systems, A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP, On a routing Open Shop Problem on two nodes with unit processing times, Solving Matching Problems Efficiently in Bipartite Graphs, Using the minimum maximum flow degree to approximate the flow coloring problem, Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs, Repeatedly matching items to agents fairly and efficiently, Just-in-Time Scheduling with Equal-Size Jobs, Arbitrary-size permutation networks using arbitrary-radix switches, Classes of perfect graphs, A complete 4-parametric complexity classification of short shop scheduling problems, Maximum matching in regular and almost regular graphs, Fair-by-design matching, Colorful strips, Path multicoloring with fewer colors in spiders and caterpillars, Decomposition of university course timetabling. A systematic study of subproblems and their complexities, Subset matching and edge coloring in bipartite graphs, New linear-time algorithms for edge-coloring planar graphs, A note on 3D orthogonal graph drawing, Chromatic scheduling in a cyclic open shop, Path problems in generalized stars, complete graphs, and brick wall graphs, Compact scheduling of zero-one time operations in multi-stage systems, Computing large matchings in planar graphs with fixed minimum degree, Automatic synthesis of quantum circuits for point addition on ordinary binary elliptic curves, Approximating the max-edge-coloring problem, Wavelength assignment in multifiber star networks, A simple algorithm for edge-coloring bipartite multigraphs, On Rearrangement of Items Stored in Stacks, TRIANGLE-FREE 2-MATCHINGS REVISITED, Complete Complexity Classification of Short Shop Scheduling, On strong proper connection number of cubic graphs, Linear algorithm for selecting an almost regular spanning subgraph in an almost regular graph, A simple matching algorithm for regular bipartite graphs., Randomized Δ-edge colouring via exchanges of complex colours
