Graph searching on some subclasses of chordal graphs (Q1578423): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:57, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Graph searching on some subclasses of chordal graphs |
scientific article |
Statements
Graph searching on some subclasses of chordal graphs (English)
0 references
12 February 2001
0 references
Graph searching is the problem of cleaning the edges of a graph by a minimum number of searchers. An edge is cleaned by having searchers on both endpoints at the same time (node search) or by moving a searcher along this edge (edge search). Lots of equivalent problems are known, for instance, one plus the pathwidth of a graph equals its node search number [\textit{N. Robertson} and \textit{P. D. Seymour}, J.\ Comb.\ Theory, Ser.\ B 35, 39-61 (1983; Zbl 0521.05062)], and edge search number and cutwidth are identical for every graph of maximum degree three [\textit{F. Makedon} and \textit{I. H. Sudborough}, Discrete Appl.\ Math.\ 23, No.\ 3, 243-265 (1989; Zbl 0715.05012)]. A starlike graph is a chordal graph obtained from a split graph by blowing up the vertices in the independent set to clique modules. Node search remains NP-complete for starlike graphs [see \textit{J. Gustedt}, Discrete Appl.\ Math.\ 45, No.\ 3, 233-248 (1993; Zbl 0798.68134)], but can be solved in time \(O(mn^k)\) on \(k\)-starlike graphs (all the clique modules have size \(k\)). Edge search is NP-complete for chordal graphs but is solvable in linear time on interval graphs, in time \(O(mn^2)\) on split graphs and in time \(O(mn^k)\) on \(k\)-starlike graphs for \(k \geq 2\).
0 references
graph searching
0 references
node search
0 references
edge search
0 references
star-like graph
0 references
split graph
0 references
interval graph
0 references
algorithm
0 references