Space-Efficient Euler Partition and Bipartite Edge Coloring

DOI10.1007/978-3-319-57586-5_27zbMath1407.68360OpenAlexW2606114807MaRDI QIDQ5283378

Torben Hagerup, Moritz Laudahn, Frank Kammer

Publication date: 21 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-57586-5_27

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (3)

Space-efficient Euler partition and bipartite edge coloring ⋮ Space-efficient biconnected components and recognition of outerplanar graphs ⋮ On-the-Fly Array Initialization in Less Space

Cites Work

• A simple optimal representation for balanced parentheses
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• A simple algorithm for edge-coloring bipartite multigraphs
• A simple matching algorithm for regular bipartite graphs.
• Succinct Representation of Balanced Parentheses and Static Trees
• Space-efficient Basic Graph Algorithms
• Near-optimal fully-dynamic graph connectivity
• Deterministic coin tossing with applications to optimal parallel list ranking
• The NP-Completeness of Edge-Coloring
• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
• On Edge Coloring Bipartite Graphs
• Using euler partitions to edge color bipartite multigraphs
• Bipartite Edge Coloring in $O(\Delta m)$ Time

This page was built for publication: Space-Efficient Euler Partition and Bipartite Edge Coloring