Cycle bases in graphs characterization, algorithms, complexity, and applications
From MaRDI portal
Publication:458496
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)
Recommendations
Cites work
- Title not available (Why is no real title available?)
- 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?)
- 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 Mathematical Model for Periodic Scheduling Problems
- A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
- A greedy approach to compute a minimum cycle basis of a directed graph
- A new approach to all-pairs shortest paths on real-weighted graphs
- 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
- 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
- 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
- STACS 2005
- Some APX-completeness results for cubic graphs
- 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
(50)- A characterization of circle graphs in terms of total unimodularity
- Is every cycle basis fundamental?
- Characterization of minimum cycle basis in weighted partial 2-trees
- How to minimize cycle times of robot manufacturing systems
- Certifying algorithms
- Games, graphs and Kirchhoff laws
- Cycle bases from orderings and coverings
- EVOLUTIONARILY-FRAGMENTED ALGORITHM FOR FINDING A MAXIMAL FLAT PART OF A GRAPH
- Acyclic digraphs giving rise to complete intersections
- Minimum cycle basis of direct product of \(K_2 \times K_n\)
- Flow and Elastic Networks on the 𝑛-Torus: Geometry, Analysis, and Computation
- On bubble generators in directed graphs
- Cycle bases of reduced powers of graphs
- Adaptive quadratures for nonlinear approximation of low-dimensional PDEs using smooth neural networks
- Properties of Gomory-Hu co-cycle bases
- Computing cyclic invariants for molecular graphs
- A cycle-based formulation and valid inequalities for DC power transmission problems with switching
- Cycle analysis of directed acyclic graphs
- Economic genome assembly from low coverage illumina and nanopore data
- Synchronization problems in computer vision with closed-form solutions
- A cycle-based formulation for the distance geometry problem
- scientific article; zbMATH DE number 2197947 (Why is no real title available?)
- Minimum spanning tree cycle intersection problem
- Convex cycle bases
- Characterising planar Cayley graphs and Cayley complexes in terms of group presentations
- A Family of Tree-Based Generators for Bubbles in Directed Graphs
- Algebraic and topological indices of molecular pathway networks in human cancers
- Sensor network localization on the group of three-dimensional displacements
- scientific article; zbMATH DE number 7053319 (Why is no real title available?)
- A computer approach to overtaking station track layout diagram design using graphs. An alternative track diagram proposal for these stations
- Minimum cycle bases of weighted outerplanar graphs
- Cycle-based formulations in distance geometry
- On minimum average stretch spanning trees in polygonal 2-trees
- Stratified sampling for the Ising model: A graph-theoretic approach
- Periodic event scheduling for automated production systems
- Forward and line-based cycle bases for periodic timetabling
- A family of tree-based generators for bubbles in directed graphs
- Cycle-based cluster variational method for direct and inverse inference
- Derivation and generation of path-based valid inequalities for transmission expansion planning
- Rooted cycle bases
- Classes of cycle bases
- The lattice of cycles of an undirected graph
- 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
- Minimum strictly fundamental cycle bases of planar graphs are hard to find
- Planarity testing and constructing the topological drawing of a plane graph (DFS)
- A posteriori error estimates for multilevel methods for graph Laplacians
- Recovering a magnitude-symmetric matrix from its principal minors
- Independent and irredundant cycle tracking sets of a graph: an efficient approach to electrical circuit analysis
- The distance orientation problem
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)
