Cycle bases in graphs characterization, algorithms, complexity, and applications
From MaRDI portal
(Redirected from Publication:458496)
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Recommendations
Cites work
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- A greedy approach to compute a minimum cycle basis of a directed graph
- A Mathematical Model for Periodic Scheduling Problems
- A new approach to all-pairs shortest paths on real-weighted graphs
- A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
- Algorithms for Generating Fundamental Cycles in a Graph
- Approximate distance oracles
- Automata, Languages and Programming
- Breaking the O(m 2 n) Barrier for Minimum Cycle Bases
- Classes of cycle bases
- Collective dynamics of `small-world' networks
- Distributed Computing: A Locality-Sensitive Approach
- Drawing graphs. Methods and models
- Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Finding short integral cycle bases for cyclic timetabling
- Finding small simple cycle separators for 2-connected planar graphs
- Geometric algorithms and combinatorial optimization
- scientific article; zbMATH DE number 2089223 (Why is no real title available?)
- scientific article; zbMATH DE number 432790 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 3508539 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 3024665 (Why is no real title available?)
- Implementing minimum cycle basis algorithms
- Inapproximability of combinatorial optimization problems
- Integral cycle bases for cyclic timetabling
- Is every cycle basis fundamental?
- Lower bounds for strictly fundamental cycle bases in grid graphs
- Lower-Stretch Spanning Trees
- Minimum cycle bases for network graphs
- Minimum cycle bases, faster and simpler
- New Approximation Algorithms for Minimum Cycle Bases of Graphs
- New length bounds for cycle bases
- Numerical solution of differential-algebraic systems arising in circuit simulation
- On cycle bases of a graph
- On finding cycle bases and fundamental cycle bases with a shortest maximal cycle
- On sparse spanners of weighted graphs
- On the approximability of the minimum strictly fundamental cycle basis problem
- On the cut polytope
- On the null-homotopy of graphs
- Periodic network optimization with different arc frequencies
- Ramanujan graphs
- Some APX-completeness results for cubic graphs
- STACS 2005
- The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
- The Moore bound for irregular graphs
- Tree spanners in planar graphs
- Undirected single-source shortest paths with positive integer weights in linear time
- Union of all the minimum cycle bases of a graph
- Visualizing Large and Clustered Networks
Cited in
(58)- Cycle bases from orderings and coverings
- Minimum cycle bases of weighted outerplanar graphs
- Construction of a topological drawing of the most planar subgraph of the non-planar graph
- Interchangeability of relevant cycles in graphs
- Acyclic digraphs giving rise to complete intersections
- A cycle-based formulation for the distance geometry problem
- The distance orientation problem
- A characterization of circle graphs in terms of total unimodularity
- Cycle analysis of directed acyclic graphs
- How to minimize cycle times of robot manufacturing systems
- Games, graphs and Kirchhoff laws
- Synchronization problems in computer vision with closed-form solutions
- The lattice of cycles of an undirected graph
- Minimum cycle basis of direct product of \(K_2 \times K_n\)
- On minimum average stretch spanning trees in polygonal 2-trees
- Characterising planar Cayley graphs and Cayley complexes in terms of group presentations
- 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
- Minimum strictly fundamental cycle bases of planar graphs are hard to find
- Derivation and generation of path-based valid inequalities for transmission expansion planning
- A cycle-based formulation and valid inequalities for DC power transmission problems with switching
- Stratified sampling for the Ising model: A graph-theoretic approach
- Convex cycle bases
- Cycle-based cluster variational method for direct and inverse inference
- Rooted cycle bases
- Sensor network localization on the group of three-dimensional displacements
- Is every cycle basis fundamental?
- Certifying algorithms
- Characterization of minimum cycle basis in weighted partial 2-trees
- Flow and Elastic Networks on the 𝑛-Torus: Geometry, Analysis, and Computation
- A Family of Tree-Based Generators for Bubbles in Directed Graphs
- A family of tree-based generators for bubbles in directed graphs
- Periodic event scheduling for automated production systems
- 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
- Independent and irredundant cycle tracking sets of a graph: an efficient approach to electrical circuit analysis
- Cycle bases of reduced powers of graphs
- scientific article; zbMATH DE number 2197947 (Why is no real title available?)
- scientific article; zbMATH DE number 7053319 (Why is no real title available?)
- On bubble generators in directed graphs
- L(p,q)-labeling and integer tension of a graph embedded on torus
- Cycle-based formulations in distance geometry
- Forward and line-based cycle bases for periodic timetabling
- Economic genome assembly from low coverage illumina and nanopore data
- Adaptive quadratures for nonlinear approximation of low-dimensional PDEs using smooth neural networks
- Computing cyclic invariants for molecular graphs
- Recovering a magnitude-symmetric matrix from its principal minors
- On the split closure of the periodic timetabling polytope
- Fast algorithms for minimum homology basis
- A note on local convergence of iterative processes for pipe network analysis
- Primitive, edge-short, isometric, and pantochordal cycles
- The tropical and zonotopal geometry of periodic timetables
- Efficient bounds tightening based on SOCP relaxations for AC optimal power flow
- Maximizing minimum cycle bases intersection
- Algebraic and topological indices of molecular pathway networks in human cancers
- Properties of Gomory-Hu co-cycle bases
- Classes of cycle bases
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)
