Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions

DOI10.1016/J.TCS.2008.07.020MaRDI QIDQ1001894zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Charis Papadopoulos

Publication date 19 February 2009

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

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

zbMATH Keywords

graph classeslinear-time algorithmsminimal completions of graphsminimal deletions of graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Single-Edge Monotonic Sequences of Graphs and Linear-Time Algorithms for Minimal Completions and Deletions
• Minimal split completions
• scientific article; zbMATH DE number 1185294
• Characterizing and Computing Minimal Cograph Completions
• Characterizing and computing minimal cograph completions

Cites work

• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 1305520 (Why is no real title available?)
• scientific article; zbMATH DE number 1107728 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
• A completely dynamic algorithm for split graphs
• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• A practical algorithm for making filled graphs minimal
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• An optimal parallel co-connectivity algorithm
• Automata, Languages and Programming
• Characterizations and algorithmic applications of chordal graph embeddings
• Characterizing Minimal Interval Completions
• Complexity classification of some edge modification problems
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Computing and Combinatorics
• Computing the Minimum Fill-In is NP-Complete
• Every monotone graph property is testable
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions
• Maximal chordal subgraphs
• Measures on monotone properties of graphs
• Minimal Interval Completion Through Graph Exploration
• Minimal Proper Interval Completions
• Minimal Split Completions of Graphs
• NP-completeness results for edge modification problems
• Node-Deletion Problems on Bipartite Graphs
• On the interval completion of chordal graphs
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Safe separators for treewidth
• Several results on chordal bipartite graphs
• Some simplified NP-complete graph problems
• Threshold graphs and related topics
• Treewidth and minimum fill-in: Grouping the minimal separators

Cited in

(11)

• Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs
• On dynamic threshold graphs and related classes
• Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
• Fully dynamically maintaining minimal integral separator for threshold and difference graphs
• Fast minimal triangulation algorithm using minimum degree criterion
• Single-Edge Monotonic Sequences of Graphs and Linear-Time Algorithms for Minimal Completions and Deletions
• Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone
• Graph modification problem for some classes of graphs
• Proximity Search for Maximal Subgraph Enumeration
• Strongly chordal and chordal bipartite graphs are sandwich monotone
• scientific article; zbMATH DE number 1185294 (Why is no real title available?)

This page was built for publication: Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions

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