Completely separable graphs
From MaRDI portal
Publication:908944
DOI10.1016/0166-218X(90)90131-UzbMath0694.05060WikidataQ127976387 ScholiaQ127976387MaRDI QIDQ908944
Frédéric Maffray, Peter L. Hammer
Publication date: 1990
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
separabilityBoolean functionsoptimization problemsrecognitionCompletely separable graphsliner time algorithmsmaximum eighted cliquemaximum weighted stable set
Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph theory (05C99) Applications of graph theory to circuits and networks (94C15)
Related Items
On computing the Galois lattice of bipartite distance hereditary graphs, PLA folding in special graph classes, Distance approximating spanning trees, Efficient parallel recognition algorithms of cographs and distance hereditary graphs, Dominating cliques in distance-hereditary graphs, Weighted efficient domination problem on some perfect graphs, Powers of distance-hereditary graphs, Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs, Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs, Total dominating sequences in trees, split graphs, and under modular decomposition, Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions, Networks with small stretch number, Finding a sun in building-free graphs, On polygon numbers of circle graphs and distance hereditary graphs, Homogeneously orderable graphs, Unique response Roman domination: complexity and algorithms, Homogeneously orderable graphs and the Steiner tree problem, Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs, Probe Ptolemaic Graphs, Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs, Make a graph singly connected by edge orientations, MAD trees and distance-hereditary graphs, Unnamed Item, Simple linear-time algorithms for counting independent sets in distance-hereditary graphs, Distance labeling scheme and split decomposition, A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs, LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem, On coloring problems with local constraints, On coloring problems with local constraints, Clique-width with an inactive label, Practical and efficient split decomposition via graph-labelled trees, Dynamic Distance Hereditary Graphs Using Split Decomposition, Finding a minimum path cover of a distance-hereditary graph in polynomial time, A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs, Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs, Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs, Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way, Solving some NP-complete problems using split decomposition, Comparing the metric and strong dimensions of graphs, Bipartite almost distance-hereditary graphs, Equistable distance-hereditary graphs, Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs, Graphs with bounded induced distance, Distance-hereditary comparability graphs, Paired-domination problem on distance-hereditary graphs, Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width, Domination graphs: Examples and counterexamples, \(O(m\log n)\) split decomposition of strongly-connected graphs, Distance-hereditary digraphs, The Hamiltonian problem on distance-hereditary graphs, Distance-hereditary graphs are clique-perfect, Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs, A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs, Domination in distance-hereditary graphs, Clique-width of graphs defined by one-vertex extensions, Weighted connected domination and Steiner trees in distance-hereditary graphs, Treelike comparability graphs, Laminar structure of ptolemaic graphs with applications, (\(k,+\))-distance-hereditary graphs, Distance-Hereditary Comparability Graphs, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Rebuilding convex sets in graphs, Computing maximum stable sets for distance-hereditary graphs, ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES, The bi-join decomposition, Knocking out \(P_k\)-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Which claw-free graphs are perfectly orderable?
- Topics on perfect graphs
- Distance-hereditary graphs
- On a property of the class of n-colorable graphs
- A Linear Recognition Algorithm for Cographs
- On brittle graphs
- A Combinatorial Decomposition Theory
- Parity Graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- Recognizing circle graphs in polynomial time
