Probe Ptolemaic Graphs

DOI10.1007/978-3-540-69733-6_46zbMath1148.05309OpenAlexW1608291091MaRDI QIDQ3511358

Van Bang Le, Ton Kloks, Sheng-Lung Peng, David B. Chandler, Maw-Shang Chang

Publication date: 10 July 2008

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

Full work available at URL: https://doi.org/10.1007/978-3-540-69733-6_46

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity ⋮ On the probe problem for \((r,\ell )\)-well-coveredness ⋮ A characterization of chain probe graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Completely separable graphs
• Probe threshold and probe trivially perfect graphs
• Distance-hereditary graphs
• Complement reducible graphs
• A simple linear time algorithm for cograph recognition
• Characterisations and Linear-Time Recognition of Probe Cographs
• Partitioned Probe Comparability Graphs
• Convexity in Graphs and Hypergraphs
• The Comparability Graph of a Tree
• A characterization of ptolemaic graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs
• A Note on "The Comparability Graph of a Tree"
• A Characterization of Certain Ptolemaic Graphs
• STACS 2005
• Computing and Combinatorics
• Algorithms and Computation
• Theory and Applications of Models of Computation
• Finding houses and holes in graphs