Recognizing a class of bicircular matroids

DOI10.1016/0166-218X(93)90112-2zbMath0777.05036WikidataQ127155267 ScholiaQ127155267MaRDI QIDQ2367405

Collette R. Coullard, Donald K. Wagner, John G. del Greco

Publication date: 10 August 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

complexitypolynomial-time algorithmNP-hardrecognition problemHalin graphsbicircular matroidgeneralized wheels

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Binary signed-graphic matroids: representations and recognition algorithms, Characterizing bias matroids, Recognizing hidden bicircular networks

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The structure of bases in bicircular matroids
• On the complexity of recognizing a class of generalized networks
• Connectivity in bicircular matroids
• Signed graphs
• Recognizing graphic matroids
• Representations of bicircular matroids
• On matroids on edge sets of graphs with connected subgraphs as circuits. II
• Infinite graphs and bicircular matroids
• Matroids from directed graphs
• Uncovering generalized-network structure in matrices
• On subgraphs as matroid cells
• Voltage-Graphic Matroids
• Combinatorial Algorithms for the Generalized Circulation Problem
• BICIRCULAR GEOMETRY AND THE LATTICE OF FORESTS OF A GRAPH
• BICIRCULAR MATROIDS