Cycle bases in graphs characterization, algorithms, complexity, and applications

DOI10.1016/j.cosrev.2009.08.001zbMath1301.05195OpenAlexW2081681998MaRDI QIDQ458496

Torsten Ueckerdt, Christian Liebchen, Kurt Mehlhorn, Dimitrios Michail, Romeo Rizzi, Telikepalli Kavitha, Katharina A. Zweig

Publication date: 7 October 2014

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

Full work available at URL: http://edoc.mpg.de/518293

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Minimum strictly fundamental cycle bases of planar graphs are hard to find, A characterization of circle graphs in terms of total unimodularity, A Family of Tree-Based Generators for Bubbles in Directed Graphs, Cycle analysis of directed acyclic graphs, Rooted Cycle Bases, How to minimize cycle times of robot manufacturing systems, Stratified sampling for the Ising model: A graph-theoretic approach, Sensor Network Localization on the Group of Three-Dimensional Displacements, Cycle-based cluster variational method for direct and inverse inference, Games, graphs and Kirchhoff laws, A computer approach to overtaking station track layout diagram design using graphs. An alternative track diagram proposal for these stations, Minimum spanning tree cycle intersection problem, A family of tree-based generators for bubbles in directed graphs, Periodic Event Scheduling for Automated Production Systems, Minimum cycle bases of weighted outerplanar graphs, Derivation and generation of path-based valid inequalities for transmission expansion planning, Cycle-based formulations in distance geometry, Synchronization problems in computer vision with closed-form solutions, Forward and line-based cycle bases for periodic timetabling, Characterising planar Cayley graphs and Cayley complexes in terms of group presentations, Certifying algorithms, The lattice of cycles of an undirected graph, Characterization of minimum cycle basis in weighted partial 2-trees, EVOLUTIONARILY-FRAGMENTED ALGORITHM FOR FINDING A MAXIMAL FLAT PART OF A GRAPH, PLANARITY TESTING AND CONSTRUCTING THE TOPOLOGICAL DRAWING OF A PLANE GRAPH (DFS), A Posteriori Error Estimates for Multilevel Methods for Graph Laplacians, Minimum cycle basis of direct product of \(K_2 \times K_n\), Acyclic digraphs giving rise to complete intersections, On bubble generators in directed graphs, Construction of a topological drawing of the most planar subgraph of the non-planar graph, \(L(p,q)\)-labeling and integer tension of a graph embedded on torus, Algebraic and topological indices of molecular pathway networks in human cancers, A cycle-based formulation for the distance geometry problem, A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching, Properties of Gomory-Hu co-cycle bases, The distance orientation problem, On minimum average stretch spanning trees in polygonal 2-trees, Unnamed Item, Flow and Elastic Networks on the 𝑛-Torus: Geometry, Analysis, and Computation

Uses Software

• PESPLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the approximability of the minimum strictly fundamental cycle basis problem
• Classes of cycle bases
• Integral cycle bases for cyclic timetabling
• On finding cycle bases and fundamental cycle bases with a shortest maximal cycle
• A greedy approach to compute a minimum cycle basis of a directed graph
• Finding small simple cycle separators for 2-connected planar graphs
• On the null-homotopy of graphs
• Ramanujan graphs
• On sparse spanners of weighted graphs
• Geometric algorithms and combinatorial optimization
• The Moore bound for irregular graphs
• Union of all the minimum cycle bases of a graph
• Some APX-completeness results for cubic graphs
• Minimum cycle bases for network graphs
• A new approach to all-pairs shortest paths on real-weighted graphs
• Periodic network optimization with different arc frequencies
• New length bounds for cycle bases
• Minimum cycle bases
• Undirected single-source shortest paths with positive integer weights in linear time
• On cycle bases of a graph
• Is every cycle basis fundamental?
• New Approximation Algorithms for Minimum Cycle Bases of Graphs
• Visualizing Large and Clustered Networks
• A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs
• Lower-Stretch Spanning Trees
• Breaking the O(m 2 n) Barrier for Minimum Cycle Bases
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• A Mathematical Model for Periodic Scheduling Problems
• Algorithms for Generating Fundamental Cycles in a Graph
• The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Distributed Computing: A Locality-Sensitive Approach
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• On the cut polytope
• Approximate distance oracles
• Lower bounds for strictly fundamental cycle bases in grid graphs
• Collective dynamics of ‘small-world’ networks
• Automata, Languages and Programming
• STACS 2005
• Algorithms - ESA 2003
• Tree spanners in planar graphs
• Drawing graphs. Methods and models