A Polynomial-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Circular-Arc Graphs

Shin-ichi NAKAYAMA

IEICE TRANSACTIONS on Information and Systems   Vol.E105-D    No.8    pp.1373-1382
Publication Date: 2022/08/01
Publicized: 2022/05/12
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2021EDP7175
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
spanning tree,  circular-arc graph,  algorithm,  

Full Text: PDF(552.6KB)>>
Buy this Article

Given a graph G=(V, E), where V and E are vertex and edge sets of G, and a subset VNT of vertices called a non-terminal set, a spanning tree with a non-terminal set VNT, denoted by STNT, is a connected and acyclic spanning subgraph of G that contains all vertices of V where each vertex in a non-terminal set is not a leaf. On general graphs, the problem of finding an STNT of G is known to be NP-hard. In this paper, we show that if G is a circular-arc graph then finding an STNT of G is polynomially solvable with respect to the number of vertices.

open access publishing via