Premium
Mixed search number and linear‐width of interval and split graphs
Author(s) -
Fomin Fedor V.,
Heggernes Pinar,
Mihai Rodica
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20373
Subject(s) - interval (graph theory) , combinatorics , mathematics , time complexity , interval graph , indifference graph , discrete mathematics , chordal graph , graph , 1 planar graph
We show that the mixed search number and the linear‐width of interval graphs and of split graphs can be computed in linear time and in polynomial time, respectively. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010