Graph Sandwich Problems
From MaRDI portal
Publication:4857542
DOI10.1006/jagm.1995.1047zbMath0838.68054OpenAlexW2029095423WikidataQ56532543 ScholiaQ56532543MaRDI QIDQ4857542
Haim Kaplan, Ron Shamir, Martin Charles Golumbic
Publication date: 27 May 1996
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/e9434610799e2bc89d9cf1b0c58dd3076adfb0fe
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
The graph sandwich problem for 1-join composition is NP-complete ⋮ Orienting graphs to optimize reachability ⋮ A general method for forbidden induced subgraph sandwich problem NP-completeness ⋮ Sandwich and probe problems for excluding paths ⋮ The homogeneous set sandwich problem ⋮ Can transitive orientation make sandwich problems easier? ⋮ On decision and optimization (\(k\),\(l\))-graph sandwich problems ⋮ The pair completion algorithm for the homogeneous set sandwich problem ⋮ Bipartite completion of colored graphs avoiding chordless cycles of given lengths ⋮ Threshold-coloring and unit-cube contact representation of planar graphs ⋮ Good characterizations and linear time recognition for 2-probe block graphs ⋮ On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs ⋮ On the forbidden induced subgraph probe and sandwich problems ⋮ The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy ⋮ The interval order polytope of a digraph ⋮ The Generalized Max-Controlled Set Problem ⋮ Characterizing and Computing Minimal Cograph Completions ⋮ Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes ⋮ Chordal bipartite completion of colored graphs ⋮ On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints ⋮ Obstructing Visibilities with One Obstacle ⋮ Algorithms and complexity of sandwich problems in graphs (extended abstract) ⋮ On the probe problem for \((r,\ell )\)-well-coveredness ⋮ On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems ⋮ A short note on the complexity of computing strong pathbreadth ⋮ On the forbidden induced subgraph sandwich problem ⋮ The chain graph sandwich problem ⋮ A characterization of chain probe graphs ⋮ Two characterizations of chain partitioned probe graphs ⋮ Partitioned probe comparability graphs ⋮ Recognition of Probe Ptolemaic Graphs ⋮ Efficiently enumerating minimal triangulations ⋮ Unique Perfect Phylogeny Is NP-Hard ⋮ Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties ⋮ The polynomial dichotomy for three nonempty part sandwich problems ⋮ The polynomial dichotomy for three nonempty part sandwich problems ⋮ The strength of Dantzig-Wolfe reformulations for the stable set and related problems ⋮ The external constraint 4 nonempty part sandwich problem ⋮ The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ Block-graph width ⋮ Competitive graph searches ⋮ Characterizing and computing minimal cograph completions ⋮ On the complexity of computing treelength ⋮ Unnamed Item ⋮ On listing, sampling, and counting the chordal graphs with edge constraints ⋮ Near-optimal solutions for the generalized max-controlled set problem ⋮ Clustering with partial information ⋮ Complexity classification of some edge modification problems ⋮ Some completion problems for graphs without chordless cycles of prescribed lengths ⋮ Clustering with Partial Information ⋮ The sandwich problem for cutsets: clique cutset, \(k\)-star cutset ⋮ On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs ⋮ On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems ⋮ On the bi-enhancement of chordal-bipartite probe graphs ⋮ Completing colored graphs to meet a target property ⋮ An improved derandomized approximation algorithm for the max-controlled set problem ⋮ On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs ⋮ Characterizing and recognizing probe block graphs ⋮ Sandwiches missing two ingredients of order four ⋮ Sandwich problem for \(\varPi\)- and \(\varDelta\)-free multigraphs and its applications to positional games ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ A vertex ordering characterization of simple-triangle graphs ⋮ The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs ⋮ A note on finding all homogeneous set sandwiches ⋮ The graph sandwich problem for \(P_4\)-sparse graphs ⋮ Weak Unit Disk and Interval Representation of Graphs ⋮ On the Complexity of Probe and Sandwich Problems for Generalized Threshold Graphs ⋮ Unnamed Item ⋮ On the proper intervalization of colored caterpillar trees ⋮ Tree Projections: Game Characterization and Computational Aspects ⋮ Skew partition sandwich problem is NP-complete ⋮ Lexicographic Orientation Algorithms ⋮ Tree-visibility orders ⋮ Matrix sandwich problems ⋮ Unnamed Item ⋮ The Proper Interval Colored Graph problem for caterpillar trees ⋮ The P4-sparse Graph Sandwich Problem ⋮ Helly Property and Sandwich Graphs ⋮ Partitions and well-coveredness: the graph sandwich problem ⋮ An efficient algorithm for solving the homogeneous set sandwich problem ⋮ Exact algorithms for intervalizing coloured graphs
