Space-efficient Euler partition and bipartite edge coloring

DOI10.1016/j.tcs.2018.01.008zbMath1407.68361OpenAlexW2789795852MaRDI QIDQ1628587

Torben Hagerup, Frank Kammer, Moritz Laudahn

Publication date: 4 December 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.01.008

zbMATH Keywords

data structuresgraph algorithmsspace efficiencybipartite edge coloringEuler partitionsubgraph stacks

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 (6)

Space-efficient vertex separators for treewidth ⋮ Sorting and ranking of self-delimiting numbers with applications to tree isomorphism ⋮ Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays. ⋮ Unnamed Item ⋮ Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster ⋮ Simple 2^f-Color Choice Dictionaries

Cites Work

• Unnamed Item
• Selection from read-only memory with limited workspace
• 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.
• Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
• Succinct Representation of Balanced Parentheses and Static Trees
• Improved Space Efficient Algorithms for BFS, DFS and Applications
• Depth-First Search Using $$O(n)$$ Bits
• Space-efficient Basic Graph Algorithms
• Near-optimal fully-dynamic graph connectivity
• 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
• Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits
• Space-Efficient Euler Partition and Bipartite Edge Coloring

This page was built for publication: Space-efficient Euler partition and bipartite edge coloring