Modifying a graph using vertex elimination

DOI10.1007/S00453-013-9848-2MaRDI QIDQ2345941zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Pim Van 't Hof, Fredrik Manne, Daniël Paulusma, Michał Pilipczuk, Petr A. Golovach

Publication date 21 May 2015

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://dro.dur.ac.uk/14116/1/14116.pdf

zbMATH Keywords

parameterized complexitygraph modification problemsvertex eliminationlinear kernel

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• Obtaining a Planar Graph by Vertex Deletion
• Obtaining a planar graph by vertex deletion
• Reducing the maximum degree of a graph by deleting vertices
• Graph modification problem for some classes of graphs
• scientific article; zbMATH DE number 2190093
• scientific article; zbMATH DE number 7057487
• Vertex removal in biclique graphs
• Editing to a connected graph of given degrees
• Editing to a connected graph of given degrees
• Edge addition and edge deletion of graphs

Cites work

• scientific article; zbMATH DE number 3816913 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 6297714 (Why is no real title available?)
• A quartic kernel for pathwidth-one vertex deletion
• Algorithmic Aspects of Vertex Elimination on Graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Chordal deletion is fixed-parameter tractable
• Complexity classification of some edge modification problems
• Dominating set is fixed parameter tractable in claw-free graphs
• Edge-Deletion Problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• How to eliminate a graph
• Measuring indifference: unit interval vertex deletion
• Minimal triangulations of graphs: a survey
• Obtaining a planar graph by vertex deletion
• On problems without polynomial kernels
• Parameterized complexity of vertex deletion into perfect graph classes
• Quickly excluding a planar graph
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Spanning Trees with Many Leaves
• The Use of Linear Graphs in Gauss Elimination
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues

Cited in

(2)

• How to eliminate a graph
• Obtaining a planar graph by vertex deletion

Describes a project that uses

Uses Software

• symrcm

This page was built for publication: Modifying a graph using vertex elimination

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