Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{635424,
author = {Obdržálek, Jan},
address = {New York/Philadelphia},
booktitle = {Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms},
keywords = {tree-width; directed tree-width; DAG-width; digraph-searching},
language = {eng},
location = {New York/Philadelphia},
isbn = {0-89871-605-5},
pages = {814--821},
publisher = {Association for Computing Machinery/Society for Industrial and Applied Mathematics},
title = {DAG-width - Connectivity Measure for Directed Graphs},
year = {2006}
}
TY - JOUR
ID - 635424
AU - Obdržálek, Jan
PY - 2006
TI - DAG-width - Connectivity Measure for Directed Graphs
PB - Association for Computing Machinery/Society for Industrial and Applied Mathematics
CY - New York/Philadelphia
SN - 0898716055
KW - tree-width
KW - directed tree-width
KW - DAG-width
KW - digraph-searching
N2 - Tree-width is a very useful connectivity measure for undirected graphs. We propose a new definition, called DAG-width, for directed graphs which measures how close a graph is to a directed acyclic graph. In addition we define a cops-and-robber game and show that this game characterises exactly the class of graphs of bounded DAG-width. A comparison of DAG-width with tree-width and directed tree-width follows. Finally we show that NP-complete problems can be solved in polynomial time on graphs of bounded DAG-width.
ER -
OBDRŽÁLEK, Jan. DAG-width - Connectivity Measure for Directed Graphs. In \textit{Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms}. New York/Philadelphia: Association for Computing Machinery/Society for Industrial and Applied Mathematics, 2006, s.~814--821. ISBN~0-89871-605-5.
|
