Name
Abstract | ||
|---|---|---|
We present an algorithm that supports operations for modifying a split graph by adding edges or vertices and deleting edges, such that after each modification the graph is repaired to become a split graph in a minimal way. In particular, if the graph is not split after the modification, the algorithm computes a minimal, or if desired even a minimum, split completion or deletion of the modified graph. The motivation for such operations is similar to the motivation for fully dynamic algorithms for particular graph classes. In our case we allow all modifications to the graph and repair, rather than allowing only the modifications that keep the graph split. Fully dynamic algorithms of the latter kind are known for split graphs [L. Ibarra, Fully dynamic algorithms for chordal graphs and split graphs, Technical Report DCS-262-IR, University of Victoria, Canada, 2000]. Our results can be used to design linear time algorithms for some recognition and completion problems, where the input is supplied in an on-line fashion. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.dam.2008.06.028 | Discrete Applied Mathematics |
Keywords | Field | DocType |
modified graph,particular graph class,dynamic algorithms,linear time algorithm,completion problem,dynamic algorithm,split completion,graph split,split graphs,on-line algorithms,minimal split completions,chordal graph,l. ibarra,split graph | Discrete mathematics,Block graph,Combinatorics,Outerplanar graph,Line graph,Null graph,Pathwidth,Mathematics,Planar graph,Complement graph,Split graph | Journal |
Volume | Issue | ISSN |
157 | 9 | Discrete Applied Mathematics |
Citations | PageRank | References |
4 | 0.39 | 24 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pinar Heggernes | 1 | 845 | 72.39 |
| Federico Mancini | 2 | 78 | 9.79 |