Speeding up Graph Algorithms via Switching Classes

DOI10.1007/978-3-319-19315-1_21zbMath1401.68254arXiv1408.4900OpenAlexW2287003322MaRDI QIDQ2946059

Nathan Lindzey

Publication date: 15 September 2015

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

Full work available at URL: https://arxiv.org/abs/1408.4900

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

On the Hardness of Switching to a Small Number of Edges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple DFS on the complement of a graph and on partially complemented digraphs
• Switching classes of directed graphs
• Simple efficient graph compression schemes for dense and complement graphs
• Modular decomposition and transitive orientation
• Clique partitions, graph compression and speeding-up algorithms
• Algorithms for dense graphs and networks on the random access computer
• On the Hardness of Decoding the Gale–Berlekamp Code
• Faster scaling algorithms for general graph matching problems
• Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
• Paths, Trees, and Flowers
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Speeding up Graph Algorithms via Switching Classes