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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom