Edge contractions in subclasses of chordal graphs

DOI10.1016/J.DAM.2011.12.012MaRDI QIDQ423902zbMATH OpenOpenAlexFDO

Authors Rémy Belmonte, Pinar Heggernes, Pim Van 't Hof

Publication date 30 May 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.12.012

zbMATH Keywords

chordal graphsedge contractionsgraph modification algorithmsinduced subgraph isomorphism

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph minors (05C83)

Recommendations

• Edge contractions in subclasses of chordal graphs
• On the structure of contractible vertex pairs in chordal graphs
• Contractible edges in subgraphs of 2-connected graphs
• On the parameterized approximability of contraction to classes of chordal graphs
• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• scientific article; zbMATH DE number 4202289
• On edge contractible graphs.
• scientific article; zbMATH DE number 3910434
• scientific article; zbMATH DE number 3918408
• Edge-matching graph contractions and their interlacing properties

Cites work

• scientific article; zbMATH DE number 3816913 (Why is no real title available?)
• scientific article; zbMATH DE number 139780 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• A Note on "The Comparability Graph of a Tree"
• Algorithmic graph theory and perfect graphs
• Containment relations in split graphs
• Contractibility and NP-completeness
• Contracting a chordal graph to a split graph or a tree
• Contractions of Planar Graphs in Polynomial Time
• Edge contractions in subclasses of chordal graphs
• Finding contractions and induced minors in chordal graphs via disjoint paths
• Graph Classes: A Survey
• Graph minors. XIII: The disjoint paths problem
• Graph theory
• Induced subgraph isomorphism on interval and proper interval graphs
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• On contracting graphs to fixed pattern graphs
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Quasi-threshold graphs
• The Comparability Graph of a Tree
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Threshold graphs and related topics

Cited in

(11)

• The micro-world of cographs
• Detecting fixed patterns in chordal graphs in polynomial time
• Necessary edges in k-chordalisations of graphs
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• The complexity of contracting bipartite graphs into small cycles
• Characterizations of cographs as intersection graphs of paths on a grid
• Contracting a chordal graph to a split graph or a tree
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Contracting chordal graphs and bipartite graphs to paths and trees
• The complexity of blocking (semi)total dominating sets with edge contractions
• Edge contractions in subclasses of chordal graphs

This page was built for publication: Edge contractions in subclasses of chordal graphs

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