Modular decomposition and transitive orientation
From MaRDI portal
Publication:1301738
DOI10.1016/S0012-365X(98)00319-7zbMath0933.05146WikidataQ57535770 ScholiaQ57535770MaRDI QIDQ1301738
Ross M. McConnell, Jeremy P. Spinrad
Publication date: 4 April 2000
Published in: Discrete Mathematics (Search for Journal in Brave)
Related Items (only showing first 100 items - show all)
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 ⋮ On approximating MIS over B1-VPG graphs* ⋮ Hierarchical and modularly-minimal vertex colorings ⋮ Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Clique-perfectness and balancedness of some graph classes ⋮ Independent sets in asteroidal triple-free graphs ⋮ More results on weighted independent domination ⋮ Speeding up Graph Algorithms via Switching Classes ⋮ Complete edge-colored permutation graphs ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ Independent set under a change constraint from an initial solution ⋮ Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs ⋮ Computing densest \(k\)-subgraph with structural parameters ⋮ Some algorithmic results for eternal vertex cover problem in graphs ⋮ On the kernel and related problems in interval digraphs ⋮ Computing and listing avoidable vertices and paths ⋮ \(st\)-orientations with few transitive edges ⋮ The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs ⋮ Partial and simultaneous transitive orientations via modular decompositions ⋮ Succinct permutation graphs ⋮ $st$-Orientations with Few Transitive Edges ⋮ Computing and listing avoidable vertices and paths ⋮ Dominance drawings for DAGs with bounded modular width ⋮ Coloring mixed and directional interval graphs ⋮ Comparability digraphs: an analogue of comparability graphs ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Computing well-covered vector spaces of graphs using modular decomposition ⋮ Parameterized Complexity of Safe Set ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ Counting spanning trees using modular decomposition ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs ⋮ How Bad is the Freedom to Flood-It? ⋮ GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH ⋮ Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes ⋮ Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs ⋮ On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem ⋮ A polynomial algorithm to find an independent set of maximum weight in a fork-free graph ⋮ Parameterized algorithms for the happy set problem ⋮ Unnamed Item ⋮ The clique operator on graphs with few \(P_{4}\)'s ⋮ Nesting of prime substructures in \(k-\)ary relations ⋮ Happy set problem on subclasses of co-comparability graphs ⋮ Improved bottleneck domination algorithms ⋮ A note on the recognition of bisplit graphs ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs ⋮ A short note on undirected Fitch graphs ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ Fully dynamic algorithm for recognition and modular decomposition of permutation graphs ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ Graph isomorphism restricted by lists ⋮ Counting Spanning Trees in Graphs Using Modular Decomposition ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ SIMPLE EXTENSIONS OF COMBINATORIAL STRUCTURES ⋮ On minimal forbidden subgraph characterizations of balanced graphs ⋮ Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes ⋮ Recognizing k-equistable Graphs in FPT Time ⋮ Linear-Time Recognition of Probe Interval Graphs ⋮ On uniqueness of a general factorization of graph properties ⋮ On Distance-3 Matchings and Induced Matchings ⋮ Path-Bicolorable Graphs ⋮ Minimal separators in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>P</mml:mi><mml:mn>4</mml:mn></mml:msub></mml:math>-tidy graphs ⋮ The recognizability of sets of graphs is a robust property ⋮ Bisplit graphs ⋮ Lexicographic Orientation Algorithms ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ Offensive alliances in graphs ⋮ Linear-time recognition of double-threshold graphs ⋮ The bi-join decomposition ⋮ The P4-sparse Graph Sandwich Problem ⋮ On maximum independent set of categorical product and ultimate categorical ratios of graphs ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ Fast Diameter Computation within Split Graphs ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs ⋮ A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs ⋮ A note on transitive orientations with maximum sets of sources and sinks ⋮ Minimal triangulations of graphs: a survey ⋮ Algorithms for the rainbow vertex coloring problem on graph classes ⋮ Two topics in tree inference: locating a phonological network effect in immediate recall and arborescence partitive set form ⋮ Note on the homogeneous set sandwich problem ⋮ Weighted independent sets in classes of \(P_6\)-free graphs ⋮ Interval decomposition lattices are balanced ⋮ On transitive orientations with restricted covering graphs ⋮ Simple DFS on the complement of a graph and on partially complemented digraphs ⋮ On independent vertex sets in subclasses of apple-free graphs ⋮ Tent and a subclass of \(P_{5}\)-free graphs ⋮ Polar graphs and maximal independent sets ⋮ A new LBFS-based algorithm for cocomparability graph recognition ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ A width parameter useful for chordal and co-comparability graphs ⋮ A recognition algorithm for simple-triangle graphs ⋮ Labelled induced subgraphs and well-quasi-ordering ⋮ Finding connected secluded subgraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Theory of 2-structures. I: Clans, basic subclasses, and morphisms
- Theory of 2-structures. II: Representation through labeled tree families
- Primitivity is hereditary for 2-structures
- A linear-time algorithm for a special case of disjoint set union
- On the X-join decomposition for undirected graphs
- Complement reducible graphs
- Partitive hypergraphs
- \(P_ 4\)-trees and substitution decomposition
- The complexity of comparability graph recognition and coloring
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
- A Fast Algorithm for the Decomposition of Graphs and Posets
- On Comparability and Permutation Graphs
- A Linear Recognition Algorithm for Cographs
- Incremental modular decomposition
- On testing isomorphism of permutation graphs
- Single Machine Scheduling with Series-Parallel Precedence Constraints
- The Recognition of Series Parallel Digraphs
- Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
- An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
- Circular permutation graphs
- A linear time algorithm to recognize circular permutation graphs
- Transitiv orientierbare Graphen
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Partially Ordered Sets
This page was built for publication: Modular decomposition and transitive orientation
