Cycle bases in graphs characterization, algorithms, complexity, and applications
From MaRDI portal
Publication:458496
DOI10.1016/J.COSREV.2009.08.001zbMATH Open1301.05195OpenAlexW2081681998MaRDI QIDQ458496FDOQ458496
Authors: Telikepalli Kavitha, Christian Liebchen, K. Mehlhorn, Dimitrios Michail, Romeo Rizzi, Torsten Ueckerdt, 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
Recommendations
Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)
Cites Work
- A Mathematical Model for Periodic Scheduling Problems
- Title not available (Why is that?)
- Collective dynamics of `small-world' networks
- Geometric algorithms and combinatorial optimization
- Some APX-completeness results for cubic graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
- Title not available (Why is that?)
- Algorithms for Generating Fundamental Cycles in a Graph
- Distributed Computing: A Locality-Sensitive Approach
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- On the approximability of the minimum strictly fundamental cycle basis problem
- Ramanujan graphs
- A new approach to all-pairs shortest paths on real-weighted graphs
- Minimum cycle bases, faster and simpler
- On the cut polytope
- Tree spanners in planar graphs
- On sparse spanners of weighted graphs
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Drawing graphs. Methods and models
- The Moore bound for irregular graphs
- Minimum cycle bases for network graphs
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- Automata, Languages and Programming
- Integral cycle bases for cyclic timetabling
- Periodic network optimization with different arc frequencies
- Finding short integral cycle bases for cyclic timetabling
- Undirected single-source shortest paths with positive integer weights in linear time
- Implementing minimum cycle basis algorithms
- On finding cycle bases and fundamental cycle bases with a shortest maximal cycle
- Finding small simple cycle separators for 2-connected planar graphs
- Numerical solution of differential-algebraic systems arising in circuit simulation
- Breaking the O(m 2 n) Barrier for Minimum Cycle Bases
- A greedy approach to compute a minimum cycle basis of a directed graph
- On the null-homotopy of graphs
- Union of all the minimum cycle bases of a graph
- New length bounds for cycle bases
- Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
- Title not available (Why is that?)
- Inapproximability of combinatorial optimization problems
- 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
- Title not available (Why is that?)
- The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
- Approximate distance oracles
- Lower bounds for strictly fundamental cycle bases in grid graphs
- STACS 2005
- Title not available (Why is that?)
- Classes of cycle bases
Cited In (50)
- Convex cycle bases
- Title not available (Why is that?)
- \(L(p,q)\)-labeling and integer tension of a graph embedded on torus
- The lattice of cycles of an undirected graph
- Minimum strictly fundamental cycle bases of planar graphs are hard to find
- Cycle bases of reduced powers of graphs
- Cycle analysis of directed acyclic graphs
- Is every cycle basis fundamental?
- Cycle bases from orderings and coverings
- Acyclic digraphs giving rise to complete intersections
- A characterization of circle graphs in terms of total unimodularity
- EVOLUTIONARILY-FRAGMENTED ALGORITHM FOR FINDING A MAXIMAL FLAT PART OF A GRAPH
- Construction of a topological drawing of the most planar subgraph of the non-planar graph
- On minimum average stretch spanning trees in polygonal 2-trees
- How to minimize cycle times of robot manufacturing systems
- Minimum cycle basis of direct product of \(K_2 \times K_n\)
- A Family of Tree-Based Generators for Bubbles in Directed Graphs
- Periodic event scheduling for automated production systems
- A family of tree-based generators for bubbles in directed graphs
- Stratified sampling for the Ising model: A graph-theoretic approach
- Forward and line-based cycle bases for periodic timetabling
- Independent and irredundant cycle tracking sets of a graph: an efficient approach to electrical circuit analysis
- Algebraic and topological indices of molecular pathway networks in human cancers
- A computer approach to overtaking station track layout diagram design using graphs. An alternative track diagram proposal for these stations
- A cycle-based formulation and valid inequalities for DC power transmission problems with switching
- Games, graphs and Kirchhoff laws
- On bubble generators in directed graphs
- Cycle-based cluster variational method for direct and inverse inference
- Classes of cycle bases
- Recovering a magnitude-symmetric matrix from its principal minors
- Planarity testing and constructing the topological drawing of a plane graph (DFS)
- Properties of Gomory-Hu co-cycle bases
- A cycle-based formulation for the distance geometry problem
- Characterising planar Cayley graphs and Cayley complexes in terms of group presentations
- Title not available (Why is that?)
- Derivation and generation of path-based valid inequalities for transmission expansion planning
- Certifying algorithms
- Economic genome assembly from low coverage illumina and nanopore data
- Rooted cycle bases
- Characterization of minimum cycle basis in weighted partial 2-trees
- Adaptive quadratures for nonlinear approximation of low-dimensional PDEs using smooth neural networks
- Computing cyclic invariants for molecular graphs
- Minimum spanning tree cycle intersection problem
- Sensor network localization on the group of three-dimensional displacements
- Flow and Elastic Networks on the 𝑛-Torus: Geometry, Analysis, and Computation
- Cycle-based formulations in distance geometry
- Synchronization problems in computer vision with closed-form solutions
- A posteriori error estimates for multilevel methods for graph Laplacians
- The distance orientation problem
- Minimum cycle bases of weighted outerplanar graphs
Uses Software
This page was built for publication: Cycle bases in graphs characterization, algorithms, complexity, and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458496)
