Pairwise Compatibility Graphs: A Survey
From MaRDI portal
Publication:3186100
DOI10.1137/140978053zbMath1342.05058OpenAlexW2477819130MaRDI QIDQ3186100
Blerina Sinaimeri, Tiziana Calamoneri
Publication date: 8 August 2016
Published in: SIAM Review (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01388533/file/SurveyPCG.pdf
Applications of graph theory (05C90) General topics of discrete mathematics in relation to computer science (68R01) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Signed and weighted graphs (05C22)
Related Items
Unnamed Item, New results on pairwise compatibility graphs, Recognition of linear and star variants of leaf powers is in P, Recognizing k -Leaf Powers in Polynomial Time, for Constant k, Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees, Pairwise compatibility graphs: complete characterization for wheels, Exact-2-relation graphs, A method for enumerating pairwise compatibility graphs with a given number of vertices, Inferring phylogenetic trees from the knowledge of rare evolutionary events, Some classes of graphs that are not PCGs, Characterizing star-PCGs, On the enumeration of minimal non-pairwise compatibility graphs, On the enumeration of minimal non-pairwise compatibility graphs, From modular decomposition trees to rooted median graphs, Mim-width. III. Graph powers and generalized distance domination problems, Some reduction operations to pairwise compatibility graphs, A survey on pairwise compatibility graphs, Linear-time recognition of double-threshold graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Towards a characterization of leaf powers by clique arrangements
- Tolerance graphs
- Structure and linear time recognition of 3-leaf powers
- Rooted directed path graphs are leaf powers
- Characterising \((k,\ell )\)-leaf powers
- Exact leaf powers
- Pairwise compatibility graphs
- The complete inclusion structure of leaf power classes
- A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers
- Characterizations of strongly chordal graphs
- A recognition algorithm for the intersection graphs of directed paths in directed trees
- Decomposition of graphical sequences and unigraphs
- NeST graphs
- Neighborhood subtree tolerance graphs
- Threshold graphs and related topics
- Exploring pairwise compatibility graphs
- On pairwise compatibility graphs having Dilworth number \(k\)
- Some remarks about leaf roots
- On graphs that are not PCGs
- The number of caterpillars
- On pairwise compatibility graphs having Dilworth number two
- A decomposition theorem for partially ordered sets
- On Graph Powers for Leaf-Labeled Trees
- ON THE PAIRWISE COMPATIBILITY PROPERTY OF SOME SUPERCLASSES OF THRESHOLD GRAPHS
- On Relaxing the Constraints in Pairwise Compatibility Graphs
- DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
- The 3-Steiner Root Problem
- Threshold tolerance graphs
- Recognizing $P_4 $-Sparse Graphs in Linear Time
- Graph Classes: A Survey
- Computing Phylogenetic Roots with Bounded Degrees and Errors
- Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs
- On Graphs That Are Not PCGs
- Structure and linear-time recognition of 4-leaf powers
- Ptolemaic Graphs and Interval Graphs Are Leaf Powers
- On k- Versus (k + 1)-Leaf Powers
- Algorithms and Computation
- Graph-Theoretic Concepts in Computer Science
