A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
From MaRDI portal
Publication:2784453
DOI10.1137/S0097539700372216zbMath0992.68065OpenAlexW2018773762MaRDI QIDQ2784453
Roded Sharan, Ron Shamir, Pavol Hell
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539700372216
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (39)
The interval-merging problem ⋮ Recognizing and representing proper interval graphs in parallel using merging and sorting ⋮ On some subclasses of interval catch digraphs ⋮ Polynomial kernels for proper interval completion and related problems ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs ⋮ Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs ⋮ A characterization of unit interval bigraphs of open and closed intervals ⋮ Integral mixed unit interval graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ A cubic vertex-kernel for \textsc{Trivially Perfect Editing} ⋮ A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs ⋮ Recognition of probe proper interval graphs ⋮ Fully dynamic representations of interval graphs ⋮ A fully dynamic graph algorithm for recognizing interval graphs ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Canonical antichains of unit interval and bipartite permutation graphs ⋮ A fully dynamic algorithm for modular decomposition and recognition of cographs. ⋮ Dynamic Distance Hereditary Graphs Using Split Decomposition ⋮ Minimal classes of graphs of unbounded clique-width ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Interval graph representation with given interval and intersection lengths ⋮ Unnamed Item ⋮ Unit Interval Graphs of Open and Closed Intervals ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs ⋮ Mixed unit interval graphs ⋮ Fully dynamic recognition algorithm and certificate for directed cographs ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ Random Generation and Enumeration of Proper Interval Graphs ⋮ A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ Fully dynamic algorithm for recognition and modular decomposition of permutation graphs ⋮ Dynamically maintaining split graphs ⋮ The clique-separator graph for chordal graphs ⋮ A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs ⋮ A dynamic distributed approach to representing proper interval graphs ⋮ Fully dynamic recognition of proper circular-arc graphs
This page was built for publication: A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
