Recognition algorithms for binary signed-graphic matroids

DOI10.1007/978-3-642-32147-4_41MaRDI QIDQ3167648zbMATH OpenOpenAlexFDO

Authors Leonidas Pitsoulis, Konstantinos Papalamprou

Publication date 2 November 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.6504

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Nonnumerical algorithms (68W05) Combinatorial optimization (90C27)

Abstract: In this paper we provide two recognition algorithms for the class of signed-graphic matroids along with necessary and sufficient conditions for a matroid to be signed-graphic. Specifically, we provide a polynomial-time algorithm which determines whether a given binary matroid is signed-graphic and an algorithm which determines whether a general matroid given by an independece oracle is binary signed-graphic.

Recommendations

• Binary signed-graphic matroids: representations and recognition algorithms
• Topics in Matroid Theory
• A new characterization of graphic matroids
• Signed-graphic matroids with all-graphic cocircuits
• Decomposition of binary signed-graphic matroids

Cited in

(11)

• Note on recognition of matroid systems
• Binary signed-graphic matroids: representations and recognition algorithms
• On characterizing the class of cographic signed-graphic matroids
• scientific article; zbMATH DE number 3862960 (Why is no real title available?)
• Recognizing Polymatroids Associated with Hypergraphs
• On recognizing frame and lifted-graphic matroids
• Pattern Recognition on Oriented Matroids
• On the basis pair graphs of signed-graphic matroids
• Small separations in pinch-graphic matroids
• Recognizing pinch-graphic matroids
• Decomposition of quaternary signed-graphic matroids

This page was built for publication: Recognition algorithms for binary signed-graphic matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167648)