Block-graph width

DOI10.1016/J.TCS.2010.10.041MaRDI QIDQ534563zbMATH OpenOpenAlexFDO

Authors Maw-Shang Chang, Ling-Ju Hung, Ton Kloks, Sheng-Lung Peng

Publication date 18 May 2011

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

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

zbMATH Keywords

parameterized algorithmsblock graphsprobe graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Structural characterization of families of graphs (05C75)

Recommendations

• Block-Graph Width
• Trivially-perfect width
• On some simple widths
• Bandwidth and density for block graphs
• Block elimination distance

Cites work

• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• A Characterization of Certain Ptolemaic Graphs
• Algorithms on Strings, Trees and Sequences
• Depth-First Search and Linear Graph Algorithms
• Graph Classes: A Survey
• Graph Sandwich Problems
• Graph-Theoretic Concepts in Computer Science
• Letter graphs and well-quasi-order by induced subgraphs
• On probe interval graphs
• On probe permutation graphs
• Ordering by Divisibility in Abstract Algebras
• Partitioned probe comparability graphs
• Probe split graphs
• Rank-width and vertex-minors
• Two tricks to triangulate chordal probe graphs in polynomial time
• Upper bounds to the clique width of graphs
• Vertex-minors, monadic second-order logic, and a conjecture by Seese

Cited in

(9)

• On some simple widths
• Block-Graph Width
• An adjacency labeling scheme based on a decomposition of trees into caterpillars
• A note proving the nullity of block graphs is unbounded
• Characterizing and recognizing probe block graphs
• Good characterizations and linear time recognition for 2-probe block graphs
• On two variants of split graphs: 2-unipolar graph and \(k\)-probe-split graph
• Trivially-perfect width
• On some FPT problems without polynomial Turing compressions

This page was built for publication: Block-graph width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q534563)