scientific article; zbMATH DE number 1456953

zbMath0938.05502MaRDI QIDQ4954442

Alain Cournier, Michel A. Habib

Publication date: 7 June 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (88)

A note on transitive orientations with maximum sets of sources and sinks ⋮ Minimal separators in \(P_4\)-sparse graphs ⋮ An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs ⋮ Computing role assignments of split graphs ⋮ Complexity of list coloring problems with a fixed total number of colors ⋮ On transitive orientations with restricted covering graphs ⋮ \(P_{4}\)-laden graphs: A new class of brittle graphs ⋮ Bi-complement reducible graphs ⋮ On semi-\(P_ 4\)-sparse graphs ⋮ Scattering number and modular decomposition ⋮ The complexity of modular decomposition of Boolean functions ⋮ The \(\{-2,-1\}\)-selfdual and decomposable tournaments ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A nice class for the vertex packing problem ⋮ The monadic second-order logic of graphs. X: Linear orderings ⋮ Total dominating sequences in trees, split graphs, and under modular decomposition ⋮ Unnamed Item ⋮ The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ On the closure of graphs under substitution ⋮ Weighted parameters in \((P_5,\overline {P_5})\)-free graphs ⋮ Minimal indecomposable graphs ⋮ Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions ⋮ Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs ⋮ On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs ⋮ On the complexity of role colouring planar graphs, trees and cographs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ A monadic second-order definition of the structure of convex hypergraphs. ⋮ Efficient parallel modular decomposition (extended abstract) ⋮ Modular decomposition of hypergraphs ⋮ Computing the hull and interval numbers in the weakly toll convexity ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ On variations of \(P_{4}\)-sparse graphs ⋮ The multiple domination and limited packing problems in graphs ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ On new algorithmic techniques for the weighted vertex coloring problem ⋮ Stability number of bull- and chair-free graphs revisited ⋮ The facets of the polytope of modules of a graph. ⋮ On the structure and stability number of \(P_{5}\)- and co-chair-free graphs ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs ⋮ Counting spanning trees using modular decomposition ⋮ 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. ⋮ (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization. ⋮ Upper bounds to the clique width of graphs ⋮ Polynomial cases for the vertex coloring problem ⋮ Efficient and Adaptive Parameterized Algorithms on Modular Decompositions ⋮ Two complexity results for the vertex coloring problem ⋮ Solving some NP-complete problems using split decomposition ⋮ Polynomial-time algorithm for isomorphism of graphs with clique-width at most three ⋮ The definition in monadic second-order logic of modular decompositions of ordered graphs ⋮ 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 ⋮ A distance measure for large graphs based on prime graphs ⋮ On the structure of (\(P_{5}\),\,gem)-free graphs ⋮ A simple linear time algorithm for cograph recognition ⋮ Linear-time modular decomposition of directed graphs ⋮ Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width ⋮ Hitting subgraphs in \(P_4\)-tidy graphs ⋮ The clique operator on graphs with few \(P_{4}\)'s ⋮ Nesting of prime substructures in \(k-\)ary relations ⋮ On the Carathéodory and exchange numbers of geodetic convexity in graphs ⋮ Structure and stability number of chair-, co-P- and gem-free graphs revisited ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Bipartite-perfect graphs ⋮ Recognition of some perfectly orderable graph classes ⋮ On minimal forbidden subgraph characterizations of balanced graphs ⋮ Algorithmic aspects of a general modular decomposition theory ⋮ Recognizing k-equistable Graphs in FPT Time ⋮ Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes ⋮ The possible cardinalities of global secure sets in cographs ⋮ Probe threshold and probe trivially perfect graphs ⋮ The clique operator on cographs and serial graphs ⋮ Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing ⋮ The recognizability of sets of graphs is a robust property ⋮ On stable cutsets in graphs ⋮ Modular decomposition and transitive orientation ⋮ Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time. ⋮ Generalized limited packings of some graphs with a limited number of \(P_4\)-partners ⋮ Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes ⋮ The bi-join decomposition ⋮ On algorithms for (\(P_5\), gem)-free graphs

This page was built for publication: