Minimal proper interval completions
DOI10.1016/J.IPL.2007.11.013zbMATH Open1185.05107DBLPjournals/ipl/RapaportST08OpenAlexW2159194941WikidataQ62046062 ScholiaQ62046062MaRDI QIDQ963366FDOQ963366
Authors: Ivan Rapaport, Karol Suchan, Ioan Todinca 
Publication date: 19 April 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2007.11.013
Recommendations
- Minimal Proper Interval Completions
- Algorithms – ESA 2005
- Minimal normal and commuting completions
- scientific article; zbMATH DE number 18526
- Minimal pairs and complete problems
- Minimal split completions
- Minimality and completions of PA
- scientific article; zbMATH DE number 4214076
- Minimal quasi-complete intersection ideals
- Tightly bounded completions
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cites Work
- Algorithms – ESA 2005
- Algorithmic graph theory and perfect graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Algorithmic Aspects of Vertex Elimination on Graphs
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
- Betweenness, orders and interval graphs
- A linear time recognition algorithm for proper interval graphs
- Separability generalizes Dirac's theorem
- Minimal fill in O(\(n^{2.69}\)) time
- Partition refinement techniques: an interesting algorithmic tool kit
- Title not available (Why is that?)
- Minimal Split Completions of Graphs
- Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions
Cited In (14)
- Minimal Interval Completion Through Graph Exploration
- An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
- Algorithms – ESA 2005
- Minimal split completions
- On finding the minimum bandwidth of interval graphs
- Minimum proper interval graphs
- An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem
- Graphs with at most two moplexes
- Characterizing Minimal Interval Completions
- A survey of the algorithmic aspects of modular decomposition
- On the proper interval completion problem within some chordal subclasses
- Minimal Proper Interval Completions
- Linear-time minimal cograph editing
- An \(O(n^2)\) time algorithm for the minimal permutation completion problem
This page was built for publication: Minimal proper interval completions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q963366)
