Characterizing star-PCGs

DOI10.1007/978-3-319-94776-1_42zbMath1459.05317arXiv1804.02895OpenAlexW2963016676MaRDI QIDQ5916258

Mingyu Xiao, Hiroshi Nagamochi

Publication date: 4 October 2018

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.02895

zbMATH Keywords

graph algorithmpolynomial-time algorithmpairwise compatibility graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (5)

New results on pairwise compatibility graphs ⋮ On star-multi-interval pairwise compatibility graphs ⋮ Some reduction operations to pairwise compatibility graphs ⋮ A survey on pairwise compatibility graphs ⋮ Linear-time recognition of double-threshold graphs

Cites Work

• Unnamed Item
• Characterising \((k,\ell )\)-leaf powers
• Pairwise compatibility graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On pairwise compatibility graphs having Dilworth number \(k\)
• Some reduction operations to pairwise compatibility graphs
• On graphs that are not PCGs
• On pairwise compatibility graphs having Dilworth number two
• On Graph Powers for Leaf-Labeled Trees
• ON THE PAIRWISE COMPATIBILITY PROPERTY OF SOME SUPERCLASSES OF THRESHOLD GRAPHS
• DISCOVERING PAIRWISE COMPATIBILITY GRAPHS
• Pairwise Compatibility Graphs: A Survey
• Computing Phylogenetic Roots with Bounded Degrees and Errors
• Triangle-Free Outerplanar 3-Graphs are Pairwise Compatibility Graphs
• A Necessary Condition and a Sufficient Condition for Pairwise Compatibility Graphs

This page was built for publication: Characterizing star-PCGs