The no-meet matroid

DOI10.1016/j.dam.2022.12.008MaRDI QIDQ6558676

Dimitri Watel, Natalia Kushik, Alessandro Maddaloni, José Neto, Walid Ben-Ameur

Publication date: 20 June 2024

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

zbMATH Keywords

complexitycyclesmatroidsorientationPCP

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Meeting times of random walks on graphs
• Laminar matroids
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Deterministic rendezvous in graphs
• Proof verification and the hardness of approximation problems
• The Minimum Satisfiability Problem
• On the Sequence of Consecutive Powers of a Matrix in a Boolean Algebra
• Testing finite-state machines: state identification and verification
• Digraphs
• Exchange systems, matchings, and transversals
• On a Class of Matroids Arising From Paths in Graphs
• On the Vector Representations of Induced Matroids
• A Short Proof of the Factor Theorem for Finite Graphs

Related Items (1)

A cops and robber game and the meeting time of synchronous directed walks

This page was built for publication: The no-meet matroid