Characterizing and recognizing probe block graphs

DOI10.1016/j.tcs.2014.12.014zbMath1315.05088OpenAlexW1986599368MaRDI QIDQ2513611

Van Bang Le, Sheng-Lung Peng

Publication date: 28 January 2015

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.12.014

zbMATH Keywords

block graphgraph modificationprobe block graphprobe graph

Mathematics Subject Classification ID

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

Related Items (4)

Good characterizations and linear time recognition for 2-probe block graphs ⋮ The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy ⋮ Betti numbers of edge ideals of some split graphs ⋮ On the complete width and edge clique cover problems

Cites Work

• Unnamed Item
• Block-graph width
• Two characterizations of chain partitioned probe graphs
• On probe permutation graphs
• On the bi-enhancement of chordal-bipartite probe graphs
• Probe threshold and probe trivially perfect graphs
• On the complexity of DNA physical mapping
• Algorithmic graph theory and perfect graphs
• Chordal probe graphs
• Graph Classes: A Survey
• Graph Sandwich Problems

This page was built for publication: Characterizing and recognizing probe block graphs