Edge contractions in subclasses of chordal graphs

DOI10.1016/J.DAM.2011.12.012zbMATH Open1243.05225OpenAlexW2086859323MaRDI QIDQ423902FDOQ423902

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

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
• On edge contractible graphs.
• scientific article; zbMATH DE number 3910434
• scientific article; zbMATH DE number 3918408
• Edge-matching graph contractions and their interlacing properties

zbMATH Keywords

chordal graphsedge contractionsgraph modification algorithmsinduced subgraph isomorphism

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• 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
• 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)