Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
Copyright policy )Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
A spanning tree \(T\) of a graph \(G=(V,E)\) is locally connected if for all \(v \in V\) the subgraph of \(G\) induced by \(N_T(v)\) is connected. \textit{L. Cai} [Discrete Appl. Math. 131, 63--75 (2003; Zbl 1022.05079)] showed that it is NP-complete to decide whether a graph has a locally connected spanning tree. Restricted to strongly chordal graphs and circular-arc graphs this problem becomes solvable in linear time, if a simple elimination ordering or arc-intersection model is provided with the input.
algorithm, interval graph, Directed path graph, strongly chordal graph, Circular-arc graph, Proper circular-arc graph, Theoretical Computer Science, Algorithm, Locally connected spanning tree, Strongly chordal graph, directed path graph, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, circular-arc graph, proper circular-arc graph, Discrete Mathematics and Combinatorics, Interval graph, Structural characterization of families of graphs, locally connected spanning tree
algorithm, interval graph, Directed path graph, strongly chordal graph, Circular-arc graph, Proper circular-arc graph, Theoretical Computer Science, Algorithm, Locally connected spanning tree, Strongly chordal graph, directed path graph, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, circular-arc graph, proper circular-arc graph, Discrete Mathematics and Combinatorics, Interval graph, Structural characterization of families of graphs, locally connected spanning tree
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!