Speeding up Graph Algorithms via Switching Classes

DOI10.1007/978-3-319-19315-1_21MaRDI QIDQ2946059zbMATH OpenOpenAlexFDO

Authors 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

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

Abstract: Given a graph $G$, a vertex switch of $vinV(G)$ results in a new graph where neighbors of $v$ become nonneighbors and vice versa. This operation gives rise to an equivalence relation over the set of labeled digraphs on $n$ vertices. The equivalence class of $G$ with respect to the switching operation is commonly referred to as $G$'s switching class. The algebraic and combinatorial properties of switching classes have been studied in depth; however, they have not been studied as thoroughly from an algorithmic point of view. The intent of this work is to further investigate the algorithmic properties of switching classes. In particular, we show that switching classes can be used to asymptotically speed up several super-linear unweighted graph algorithms. The current techniques for speeding up graph algorithms are all somewhat involved insofar that they employ sophisticated pre-processing, data-structures, or use "word tricks" on the RAM model to achieve at most a $O(log(n))$ speed up for sufficiently dense graphs. Our methods are much simpler and can result in super-polylogarithmic speedups. In particular, we achieve better bounds for diameter, transitive closure, bipartite maximum matching, and general maximum matching.

Recommendations

• On the speed of algebraically defined graph classes
• scientific article; zbMATH DE number 4068310
• scientific article; zbMATH DE number 3874635
• Deriving efficient graph algorithms
• On switching classes of graphs
• Fast dynamic graph algorithms for parameterized problems
• Optimally fast shortest path algorithms for some classes of graphs
• Sparsification—a technique for speeding up dynamic graph algorithms
• Faster network algorithms based on graph decomposition
• Switching classes of directed graphs

Cites work

• Algorithms for dense graphs and networks on the random access computer
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Clique partitions, graph compression and speeding-up algorithms
• Faster scaling algorithms for general graph matching problems
• scientific article; zbMATH DE number 3547309 (Why is no real title available?)
• scientific article; zbMATH DE number 1086495 (Why is no real title available?)
• scientific article; zbMATH DE number 1753166 (Why is no real title available?)
• Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
• Modular decomposition and transitive orientation
• On the Hardness of Decoding the Gale–Berlekamp Code
• Parameterized problems related to Seidel's switching
• Paths, Trees, and Flowers
• Simple DFS on the complement of a graph and on partially complemented digraphs
• Simple efficient graph compression schemes for dense and complement graphs
• Switching classes of directed graphs

Cited in

(3)

• On the speed of algebraically defined graph classes
• On the hardness of switching to a small number of edges
• On the hardness of switching to a small number of edges

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946059)