On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs

DOI10.1016/S0304-3975(96)00220-4zbMath0893.05017MaRDI QIDQ1390873

Vassilis Giakoumakis, Jean-Marie Vanherpe

Publication date: 22 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

NP-completerecognition algorithm\(P_4\)-sparse graphs\(P_4\)-reducible graphunique tree representation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (21)

Minimal separators in \(P_4\)-sparse graphs ⋮ On realization graphs of degree sequences ⋮ Recognizing well covered graphs of families with special \(P _{4}\)-components ⋮ BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES ⋮ Hierarchical and modularly-minimal vertex colorings ⋮ Spiders and their kin: an investigation of Stanley's chromatic symmetric function for spiders and related graphs ⋮ On bipartite graphs with weak density of some subgraphs ⋮ Solving larger maximum clique problems using parallel quantum annealing ⋮ Partitioning \(P_4\)-tidy graphs into a stable set and a forest ⋮ On variations of \(P_{4}\)-sparse graphs ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ Unnamed Item ⋮ The clique operator on graphs with few \(P_{4}\)'s ⋮ Finding houses and holes in graphs ⋮ Structure and stability number of chair-, co-P- and gem-free graphs revisited ⋮ Triangulating graphs with few \(P_4\)'s ⋮ ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S ⋮ A representation for the modular-pairs of a P4-reducible graph by modular decomposition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time recognition algorithm for \(P_{4}\)-reducible graphs
• Weakly triangulated graphs
• A tree representation for \(P_ 4\)-sparse graphs
• \(P_ 4\)-trees and substitution decomposition
• A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• On the computational power of pushdown automata
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A Fast Algorithm for the Decomposition of Graphs and Posets
• A Linear Recognition Algorithm for Cographs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Transitiv orientierbare Graphen

This page was built for publication: On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs