Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
type: Item
instance of: scholarly article
title: Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
zbMATH Open document ID: 1161.68040
author: Pinar Heggernes
author: Charis Papadopoulos
published in: Theoretical Computer Science
publication date: 2009-02-19T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5509584
zbMATH Keywords: linear-time algorithms
zbMATH Keywords: minimal completions of graphs
zbMATH Keywords: minimal deletions of graphs
zbMATH Keywords: graph classes
MaRDI profile type: Publication
full work available at URL: j.tcs.2008.07.020
OpenAlex ID: W2010621321
cites work: Every monotone graph property is testable
cites work: Several results on chordal bipartite graphs
cites work: Measures on monotone properties of graphs
cites work: A practical algorithm for making filled graphs minimal
cites work: Safe separators for treewidth
cites work: Treewidth and minimum fill-in: Grouping the minimal separators
cites work: NP-completeness results for edge modification problems
cites work: An optimal parallel co-connectivity algorithm
cites work: Q4373676
cites work: Maximal chordal subgraphs
cites work: A Linear-Time Algorithm for Finding a Maximal Planar Subgraph
cites work: Automata, Languages and Programming
cites work: Q4193514
cites work: Some simplified NP-complete graph problems
cites work: Algorithmic graph theory and perfect graphs
cites work: Minimal Split Completions of Graphs
cites work: A completely dynamic algorithm for split graphs
cites work: Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions
cites work: Characterizing Minimal Interval Completions
cites work: Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
cites work: Computing and Combinatorics
cites work: Q4252412
cites work: Linear time algorithms for graph search and connectivity determination on complement graphs.
cites work: Threshold graphs and related topics
cites work: Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
cites work: Complexity classification of some edge modification problems
cites work: Characterizations and algorithmic applications of chordal graph embeddings
cites work: On the interval completion of chordal graphs
cites work: Minimal Proper Interval Completions
cites work: Q5683627
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: A fully dynamic algorithm for modular decomposition and recognition of cographs.
cites work: Minimal Interval Completion Through Graph Exploration
cites work: Computing the Minimum Fill-In is NP-Complete
cites work: Node-Deletion Problems on Bipartite Graphs
DOI: 10.1016/J.TCS.2008.07.020
description: scientific article; zbMATH DE number 5509584