Computing the forcing spectrum of outerplanar graphs in polynomial time

DOI10.1016/J.DAM.2025.06.063MaRDI QIDQ6928003zbMATH OpenFDO

Authors Maximilian Gorsky, Fabian Kreßin

Publication date 17 September 2025

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

Full work available at URL https://doi.org/10.1016/J.DAM.2025.06.063

zbMATH Keywords

forcing numberforcing spectrumouterplanar graphsperfect matchingpolynomial time algorithmtight cut decomposition

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cites work

• A Minimax Theorem for Directed Graphs
• An O ( VE ) algorithm for ear decompositions of matching-covered graphs
• Anti-forcing numbers of perfect matchings of graphs
• Anti-forcing spectra of perfect matchings of graphs
• Applications of perfect matchings in chemistry
• Centroids, Representations, and Submodular Flows
• Computing the forcing and anti-forcing numbers of perfect matchings for graphs by integer linear programmings
• Continuous forcing spectra of even polygonal chains
• Digraphs of directed treewidth one
• Forcing and anti-forcing polynomials of a type of polyomino graphs
• Forcing and anti-forcing polynomials of perfect matchings for some rectangle grids
• Forcing and anti-forcing polynomials of perfect matchings of a pyrene system
• Forcing matchings on square grids
• Graph theory with applications
• Hexagonal systems with forcing single edges
• scientific article; zbMATH DE number 6127683 (Why is no real title available?)
• scientific article; zbMATH DE number 6749543 (Why is no real title available?)
• Matching structure and the matching lattice
• Matching theory
• Matching theory and Barnette's conjecture
• Non-separable and planar graphs.
• On n-extendable graphs
• On the anti-forcing number of benzenoids
• On the forced matching numbers of bipartite graphs
• On the spectrum of the forced matching number of graphs
• Reducibility among combinatorial problems
• The Complexity of Enumeration and Reliability Problems
• The forcing number of toroidal polyhexes
• The forcing polynomial of catacondensed hexagonal systems

This page was built for publication: Computing the forcing spectrum of outerplanar graphs in polynomial time

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