Solving the maximum internal spanning tree problem on interval graphs in polynomial time.
Xingfu LiHaodi FengHaitao JiangBinhai ZhuPublished in: Theor. Comput. Sci. (2018)
Keyphrases
- interval data
- spanning tree
- minmax regret
- polynomial time complexity
- graph isomorphism
- bounded treewidth
- computational complexity
- graph theory
- graph matching
- special case
- graph representation
- internal and external
- directed graph
- combinatorial optimization
- np complete problems
- np complete
- planar graphs
- search algorithm