scientific article
From MaRDI portal
Publication:3128916
zbMath0867.05068MaRDI QIDQ3128916
Ross M. McConnell, Jeremy P. Spinrad
Publication date: 3 August 1997
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
digraphcomparability graphassignmentmodulemodular decompositionpermutation graphslinear-time algorithmpermutation graphtransitive orientationcongruence partitionsprime tree decomposition
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (70)
A note on transitive orientations with maximum sets of sources and sinks ⋮ The graph sandwich problem for 1-join composition is NP-complete ⋮ Minimal separators in \(P_4\)-sparse graphs ⋮ A \(k\)-structure generalization of the theory of 2-structures ⋮ Computing a poset from its realizer ⋮ Computing role assignments of split graphs ⋮ The homogeneous set sandwich problem ⋮ The pair completion algorithm for the homogeneous set sandwich problem ⋮ Complexity of list coloring problems with a fixed total number of colors ⋮ On transitive orientations with restricted covering graphs ⋮ An Analytic Propositional Proof System on Graphs ⋮ An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures ⋮ A Characterization of b-Perfect Graphs ⋮ The complexity of modular decomposition of Boolean functions ⋮ A nice class for the vertex packing problem ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Unnamed Item ⋮ The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ Robinsonian matrices: recognition challenges ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ On the toll number of a graph ⋮ Weighted domination of cocomparability graphs ⋮ Weighted parameters in \((P_5,\overline {P_5})\)-free graphs ⋮ On the convexity number of graphs ⋮ A width parameter useful for chordal and co-comparability graphs ⋮ Planar stage graphs: Characterizations and applications ⋮ On the complexity of role colouring planar graphs, trees and cographs ⋮ On the hull number on cycle convexity of graphs ⋮ Efficient parallel modular decomposition (extended abstract) ⋮ Modular decomposition of hypergraphs ⋮ Computing the hull and interval numbers in the weakly toll convexity ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Stability number of bull- and chair-free graphs revisited ⋮ Matrix partitions of perfect graphs ⋮ On structural parameterizations of Node Kayles ⋮ The facets of the polytope of modules of a graph. ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ A cubic-vertex kernel for flip consensus tree ⋮ Graph-based data clustering with overlaps ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Recognition and isomorphism of tree-like \(P_4\)-connected graphs ⋮ A fully dynamic algorithm for modular decomposition and recognition of cographs. ⋮ Counting independent sets in cocomparability graphs ⋮ On the \(P_4\)-components of graphs ⋮ A tight lower bound for primitivity in k-structures ⋮ Odd Holes in Bull-Free Graphs ⋮ Efficient and Adaptive Parameterized Algorithms on Modular Decompositions ⋮ Matching cutsets in graphs of diameter 2 ⋮ An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\) ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ Constant thresholds can make target set selection tractable ⋮ Minimal separators in extended \(P_4\)-laden graphs ⋮ Some remarks on the geodetic number of a graph ⋮ A simple linear time algorithm for cograph recognition ⋮ Linear-time modular decomposition of directed graphs ⋮ The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness ⋮ Finding houses and holes in graphs ⋮ Nesting of prime substructures in \(k-\)ary relations ⋮ Applying modular decomposition to parameterized cluster editing problems ⋮ An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs ⋮ On the Carathéodory and exchange numbers of geodetic convexity in graphs ⋮ The possible cardinalities of global secure sets in cographs ⋮ Grundy dominating sequences on \(X\)-join product ⋮ Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing ⋮ On the computation of the hull number of a graph ⋮ The recognizability of sets of graphs is a robust property ⋮ Stability in \(P_5\)- and banner-free graphs ⋮ On stable cutsets in graphs ⋮ Modular decomposition and transitive orientation ⋮ List matrix partitions of chordal graphs
This page was built for publication:
