Finding a Minimum Circuit in a Graph

DOI10.1137/0207033zbMath0386.68064OpenAlexW1991858502WikidataQ29041951 ScholiaQ29041951MaRDI QIDQ4167596

Publication date: 1978

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0207033

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Algorithms in computer science (68W99)

Related Items (max. 100)

Computing and listing avoidable vertices and paths ⋮ Parameterized algorithms for feedback set problems and their duals in tournaments ⋮ On triangle estimation using tripartite independent set queries ⋮ Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices ⋮ Counting Subgraphs in Degenerate Graphs ⋮ Finding and counting small induced subgraphs efficiently ⋮ Dynamic Set Intersection ⋮ Map graphs having witnesses of large girth ⋮ The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics ⋮ Efficient enumeration of graph orientations with sources ⋮ Improving quantum query complexity of Boolean matrix multiplication using graph collision ⋮ Generating connected acyclic digraphs uniformly at random ⋮ A nice class for the vertex packing problem ⋮ The jogger's problem ⋮ The Null Space Problem I. Complexity ⋮ Quantum algorithm for triangle finding in sparse graphs ⋮ Quantum Complexity of Boolean Matrix Multiplication and Related Problems ⋮ Algorithms Solving the Matching Cut Problem ⋮ Parameterized complexity of \(k\)-Chinese postman problem ⋮ Mind the gap! ⋮ Induced subgraph isomorphism: are some patterns substantially easier than others? ⋮ A weighted perfect matching with constraints on weights of its parts ⋮ Counting Homomorphic Cycles in Degenerate Graphs ⋮ On the negative cost girth problem in planar networks ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Approximately Counting Triangles in Sublinear Time ⋮ Computing and listing avoidable vertices and paths ⋮ Approximate core allocations for edge cover games ⋮ Algorithms solving the matching cut problem ⋮ A simple algorithm for finding a cycle of length greater than three and without diagonals ⋮ Complexity of finding graph roots with girth conditions ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ A shortest cycle for each vertex of a graph ⋮ Finding small complete subgraphs efficiently ⋮ Dominoes ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Lengths of words accepted by nondeterministic finite automata ⋮ Star-Shaped and L-Shaped Orthogonal Drawings ⋮ Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs ⋮ Are unique subgraphs not easier to find? ⋮ Extended dynamic subgraph statistics using \(h\)-index parameterized data structures ⋮ Unnamed Item ⋮ A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques ⋮ Online recognition of dictionary with one gap ⋮ An efficient algorithm for testing goal-minimality of graphs ⋮ Finding and counting small induced subgraphs efficiently ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Planar orientations with low out-degree and compaction of adjacency matrices ⋮ Finding even cycles even faster ⋮ Efficient algorithms for subgraph listing ⋮ A fast deterministic detection of small pattern graphs in graphs without large cliques ⋮ An efficient exact algorithm for triangle listing in large graphs ⋮ Finding and counting given length cycles ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Maximum cardinality neighbourly sets in quadrilateral free graphs ⋮ Open problems around exact algorithms ⋮ Main-memory triangle computations for very large (sparse (power-law)) graphs ⋮ Unnamed Item ⋮ Decomposition plans for geometric constraint systems. I: Performance measures for CAD ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ Algebraic methods in the congested clique ⋮ On the complexity of fixed parameter clique and dominating set ⋮ Unnamed Item ⋮ Efficient algorithms for clique problems ⋮ Bottleneck subset-type restricted matching problems ⋮ Efficient approximation algorithms for shortest cycles in undirected graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized aspects of triangle enumeration ⋮ Letter graphs and geometric grid classes of permutations: characterization and recognition ⋮ Uniform random generation of large acyclic digraphs ⋮ Counting Subgraphs in Relational Event Graphs ⋮ Into the square: on the complexity of some quadratic-time solvable problems ⋮ Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs ⋮ Detecting and enumerating small induced subgraphs in \(c\)-closed graphs ⋮ Detecting directed 4-cycles still faster ⋮ Rare siblings speed-up deterministic detection and counting of small pattern graphs ⋮ An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs ⋮ Clique Counting in MapReduce ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Improved simulation of nondeterministic Turing machines ⋮ Why Do Simple Algorithms for Triangle Enumeration Work in the Real World? ⋮ Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs ⋮ Linear time algorithms for finding a dominating set of fixed size in degenerated graphs ⋮ Complex network filtering and compression algorithm based on triangle-subgraph ⋮ Time Windowed Data Structures for Graphs ⋮ The complexity of determining a shortest cycle of even length ⋮ Unique subgraphs are not easier to find ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Unnamed Item ⋮ Floorplanning by graph dualization: \(L\)-shaped modules ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication ⋮ Random Generation of Directed Acyclic Graphs ⋮ A comparative study of dictionary matching with gaps: limitations, techniques and challenges

This page was built for publication: Finding a Minimum Circuit in a Graph