Edge-Coloring Bipartite Multigraphs in O(E logD) Time

No abstract is available for this paper.

• Publication year

  1999

• Venue

  Comb.

• Publication date

  1999-09-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/S004930170002
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Edge-Coloring Bipartite Graphs

  2000cited by this paper
• Edge-Coloring Algorithms

  1995cited by this paper
• Two Problems in Graph Theory

  1982cited by this paper
• A fast parallel algorithm for routing in permutation networks

  1981cited by this paper
• The NP-Completeness of Edge-Coloring

  1981cited by this paper
• On Edge Coloring Bipartite Graphs

  1980cited by this paper
• Algorithms for edge coloring bipartite graphs

  1978cited by this paper
• A n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs

  1971cited by this paper

• Optimizing Timeliness for Distributed Stream Processing via Coflow Transmission

  2026cites this paper
• Fast and simple (1 + ε)Δ-edge-coloring of dense graphs

  2025cites this paper
• Fifty years of research in scheduling - Theory and applications

  2025cites this paper
• Improved Streaming Edge Coloring

  2025cites this paper
• The planar edge-coloring theorem of Vizing in O(n log n) time

  2025cites this paper
• Vizing's Theorem in Deterministic Almost-Linear Time

  2025cites this paper
• Edge coloring bipartite multigraphs for dynamically configuring optical switches

  2025cites this paper
• Vizing’s Theorem in Near-Linear Time

  2024cites this paper
• Faster Vizing and Near-Vizing Edge Coloring Algorithms

  2024cites this paper
• Deterministic Dynamic Edge-Colouring

  2024cites this paper
• Faster $(\Delta+1)$-Edge Coloring: Breaking the $m\sqrt{n}$ Time Barrier

  2024cites this paper
• Even Faster $(\Delta + 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains

  2024cites this paper
• Rent Division with Picky Roommates

  2024cites this paper
• Edge-coloring sparse graphs with $\Delta$ colors in quasilinear time

  2024cites this paper
• Deterministic Simple $(\Delta+\varepsilon\alpha)$-Edge-Coloring in Near-Linear Time

  2024cites this paper
• Sparsity-Parameterised Dynamic Edge Colouring

  2023cites this paper
• Fast algorithms for Vizing's theorem on bounded degree graphs

  2023cites this paper
• Edge-Coloring Algorithms for Bounded Degree Multigraphs

  2023cites this paper
• 5-List Coloring Toroidal 6-Regular Triangulations in Linear Time

  2023cites this paper
• On the network design and control of an optical network: interconnecting multiple chips on a wafer

  2023cites this paper
• On b-Matching and Fully-Dynamic Maximum k-Edge Coloring

  2023influential citation
• Arbitrary-size permutation networks using arbitrary-radix switches

  2023cites this paper
• Repeatedly Matching Items to Agents Fairly and Efficiently

  2022cites this paper
• Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities

  2022cites this paper
• The Power of Multi-step Vizing Chains

  2022cites this paper
• General Open Shop Scheduling

  2021cites this paper
• Multiprocessor Operations

  2021cites this paper
• The Greedy Algorithm is \emph{not} Optimal for On-Line Edge Coloring

  2021cites this paper
• Using the minimum maximum flow degree to approximate the flow coloring problem

  2021cites this paper
• Matching Theory Under Uncertainty

  2021cites this paper
• Decomposing a graph into subgraphs with small components

  2021cites this paper
• Compact Scheduling of Open Shops

  2021cites this paper
• 5-list Coloring Toroidal 6-regular Triangulations in Linear Time

  2021cites this paper
• Reallocation Problems with Minimum Completion Time

  2021cites this paper
• Preliminaries

  2021cites this paper
• On Rearrangement of Items Stored in Stacks

  2020cites this paper
• Finding large matchings in 1-planar graphs of minimum degree 3

  2020cites this paper
• Online Edge Coloring Algorithms via the Nibble Method

  2020cites this paper
• A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP

  2020cites this paper
• Rubik Tables and object rearrangement

  2020cites this paper
• On a Routing Open Shop Problem on Two Nodes with Unit Processing Times

  2020cites this paper
• Tight Bounds for Online Edge Coloring

  2019cites this paper
• A Randomized Algorithm for Edge-Colouring Graphs in O(m√n) Time

  2019cites this paper
• Words of Minimum Rank in Deterministic Finite Automata

  2019cites this paper
• Decomposition of university course timetabling

  2019cites this paper
• Routing Open Shop with Two Nodes, Unit Processing Times and Equal Number of Jobs and Machines

  2019cites this paper
• A Parallel Route Assignment Algorithm for Fault-Tolerant Clos Networks in OTN Switches

  2019cites this paper
• Vehicle-to-vehicle wireless power transfer: Paving the way toward an electrified transportation system

  2019cites this paper
• Data staging for efficient high throughput stream processing

  2019cites this paper
• AN ALGORITHM WITH PARAMETERIZED COMPLEXITY OF CONSTRUCTING THE OPTIMAL SCHEDULE FOR THE ROUTING OPEN SHOP PROBLEM WITH UNIT EXECUTION TIMES

  2019influential citation
• An Asymptoti Approximation S heme for Multigraph Edge Coloring

  2019cites this paper
• On strong proper connection number of cubic graphs

  2019cites this paper
• Resource Allocation in Multigranular Optical Networks

  2019cites this paper
• Time complexity analysis of RLS and (1 + 1) EA for the edge coloring problem

  2019cites this paper
• Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis

  2019influential citation
• Complexity and Algorithms

  2018cites this paper
• Fair-by-design matching

  2018cites this paper
• Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids in Mostly Sub-Quadratic Time

  2018cites this paper
• Chapter 16 – Switch Fabric

  2018cites this paper
• Perfect Matchings in Õ (n1.5) Time in Regular Bipartite Graphs

  2018cites this paper
• GRAPH COLORINGS

  2018cites this paper
• Software-defined datacenter network debugging

  2018cites this paper
• Randomized Online Matching in Regular Graphs

  2018cites this paper
• Fair-by-design algorithms: matching problems and beyond

  2018cites this paper
• C O ] 1 5 N ov 2 01 8 Terminal-Pairability in Complete Bipartite Graphs with Non-Bipartite Demands Edge-disjoint paths in complete bipartite graphs

  2018cites this paper
• On the Fundamental Limits of Coded Data Shuffling for Distributed Machine Learning

  2018cites this paper
• Delay-Constrained Input-Queued Switch

  2018influential citation
• On the Fundamental Limits of Coded Data Shuffling

  2018cites this paper
• Analysis of an algorithm for finding perfect matching in k-regular bipartite graphs

  2017cites this paper
• Extremal solutions to some art gallery and terminal-pairability problems

  2017cites this paper
• Extending Partial Representations of Trapezoid Graphs

  2017cites this paper
• Space-Efficient Euler Partition and Bipartite Edge Coloring

  2017cites this paper
• Optimal Joint Routing and Scheduling in Millimeter-Wave Cellular Networks

  2017cites this paper
• Multicast Routing and Wavelength Assignment in AWG-Based Clos Networks

  2017cites this paper
• Terminal-pairability in complete bipartite graphs with non-bipartite demands: Edge-disjoint paths in complete bipartite graphs

  2017cites this paper
• Centralized performance control for datacenter networks

  2017cites this paper
• Restricted open shop scheduling

  2017cites this paper
• Evaluation and performance modeling of two OXC architectures

  2016cites this paper
• Subset matching and edge coloring in bipartite graphs

  2016cites this paper
• Arbitrary streaming permutations with minimum memory and latency

  2016cites this paper
• A fixed-parameter algorithm for a routing open shop problem: unit processing times, few machines and locations

  2016cites this paper
• Non-blocking frame based multicast scheduler for IQ switches

  2016cites this paper
• The present and future of de novo whole-genome assembly

  2016cites this paper
• Generalized edge-colorings of weighted graphs

  2016cites this paper
• A Practical Large-Capacity Three-Stage Buffered Clos-Network Switch Architecture

  2016cites this paper
• Automatic Generation of Efficient Parallel Streaming Structures for Hardware Implementation

  2016cites this paper
• Trees, Paths, Stars, Caterpillars and Spiders

  2016cites this paper
• Joint transmission in cellular networks with CoMP - Stability and scheduling algorithms

  2015cites this paper
• Edge-Colorings of Weighted Graphs - (Extended Abstract)

  2015cites this paper
• Towards the boundary between easy and hard control problems in multicast Clos networks

  2015cites this paper
• A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job

  2015cites this paper
• Trees, Paths, Stars, Caterpillars and Spiders

  2015cites this paper
• Two Algorithms for Finding Edge Colorings in Regular Bipartite Two Algorithms for Finding Edge Colorings in Regular Bipartite Multigraphs Multigraphs

  2015cites this paper
• CherryPick: tracing packet trajectory in software-defined datacenter networks

  2015cites this paper
• Approximating the Regular Graphic TSP in Near Linear Time

  2014cites this paper
• Matchings, Random Walks, and Sampling

  2014cites this paper
• Optimal communication scheduling for iterative decoding of irregular codes

  2014cites this paper
• Guaranteed Service Independent of the Task Placement in NoCs with Torus Topology

  2014cites this paper
• Solving Matching Problems Efficiently in Bipartite Graphs

  2014cites this paper
• On the performance of edge coloring algorithms for cubic graphs

  2014cites this paper