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

Shin Ichi Nakayama, Shigeru Masuyama

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)1373-1382
Number of pages10
JournalIEICE Transactions on Information and Systems
VolumeE105D
Issue number8
DOIs
Publication statusPublished - Aug 2022

Keywords

  • algorithm
  • circular-arc graph
  • spanning tree

Fingerprint

Dive into the research topics of 'A Polynomial-Time Algorithm for Finding a Spanning Tree with Non-Terminal Set VNT on Circular-Arc Graphs'. Together they form a unique fingerprint.

Cite this