scientific article; zbMATH DE number 1420899

MaRDI QIDQ4944968zbMATH OpenFDO

Authors Assaf Natanzon, Ron Shamir, Roded Sharan

Publication date 14 January 2001

zbMATH Keywords

bounded degree graphsedge modification problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• NP-completeness results for edge modification problems
• Cluster editing with locally bounded modifications
• Cluster graph modification problems
• scientific article; zbMATH DE number 1953109
• Graph modification problem for some classes of graphs

Cited in

(7)

• Parameterizing above or below guaranteed values
• Parameterized complexity of finding subgraphs with hereditary properties.
• Complexity of edge monitoring on some graph classes
• NP-completeness results for edge modification problems
• Graph modification problem for some classes of graphs
• Complexity classification of some edge modification problems
• On the effectiveness of the incremental approach to minimal chordal edge modification

This page was built for publication:

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