The sandwich problem for decompositions and almost monotone properties
From MaRDI portal
Publication:1799213
DOI10.1007/s00453-018-0409-6zbMath1397.05186OpenAlexW2786005642MaRDI QIDQ1799213
Sophie Spirkl, Maria Chudnovsky, Celina M. Herrera de Figueiredo
Publication date: 18 October 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0409-6
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- The homogeneous set sandwich problem
- On the forbidden induced subgraph sandwich problem
- The three-in-a-tree problem
- An algorithm for finding homogeneous pairs
- On rigid circuit graphs
- The strong perfect graph theorem
- The complexity of colouring problems on dense graphs
- Star-cutsets and perfect graphs
- An algorithm for finding clique cut-sets
- Alpha-balanced graphs and matrices and GF(3)-representability of matroids
- \(P_ 4\)-trees and substitution decomposition
- On probe interval graphs
- On stable cutsets in graphs
- The graph sandwich problem for 1-join composition is NP-complete
- On the forbidden induced subgraph probe and sandwich problems
- Chordal probe graphs
- Recognizing Berge graphs
- The sandwich problem for cutsets: clique cutset, \(k\)-star cutset
- Skew partition sandwich problem is NP-complete
- Even-hole-free graphs part II: Recognition algorithm
- Recognizing decomposable graphs
- Detecting a Theta or a Prism
- Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
- Decomposition of Directed Graphs
- Complexity and algorithms for reasoning about time
- List Partitions
- Graph Sandwich Problems
- Matching cutsets in graphs
- Fast Skew Partition Recognition
- Algorithms for Perfectly Contractile Graphs
- Berge trigraphs
This page was built for publication: The sandwich problem for decompositions and almost monotone properties
