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

DOI10.1016/j.tcs.2008.07.020zbMath1161.68040OpenAlexW2010621321MaRDI QIDQ1001894

Charis Papadopoulos, Pinar Heggernes

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

linear-time algorithmsgraph classesminimal completions of graphsminimal deletions of graphs

Mathematics Subject Classification ID

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

Related Items (9)

Proximity Search for Maximal Subgraph Enumeration ⋮ Graph modification problem for some classes of graphs ⋮ Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone ⋮ Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes ⋮ Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs ⋮ On dynamic threshold graphs and related classes ⋮ Strongly chordal and chordal bipartite graphs are sandwich monotone ⋮ Fast minimal triangulation algorithm using minimum degree criterion ⋮ Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs

Cites Work

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

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