Graph searching and interval completion

DOI10.1137/S0895480199350477MaRDI QIDQ2706178zbMATH OpenFDO

Authors Fedor V. Fomin, Petr A. Golovach

Publication date 19 March 2001

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480199350477

zbMATH Keywords

profilegraph searchingcographvertex separationsearch costlinear layoutinterval graph completion

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• Interval graphs and searching
• Searching expenditure and interval graphs
• On minimum cost edge searching
• SOFSEM 2006: Theory and Practice of Computer Science
• Searching is not jumping.

Cited in

(23)

• On minimum cost edge searching
• scientific article; zbMATH DE number 1375600 (Why is no real title available?)
• Minimal interval completion through graph exploration
• On tradeoffs between width- and fill-like graph parameters
• An annotated bibliography on guaranteed graph searching
• Maximum vertex occupation time and inert fugitive: Recontamination does help
• scientific article; zbMATH DE number 1472189 (Why is no real title available?)
• Computational graph completion
• Profile minimization on compositions of graphs
• Fixed-parameter complexity of minimum profile problems
• A cops and robber game and the meeting time of synchronous directed walks
• On the domination search number
• Time constrained graph searching
• Digraph searching, directed vertex separation and directed pathwidth
• On the interval completion of chordal graphs
• On the monotonicity of games generated by symmetric submodular functions.
• Network decontamination with temporal immunity by cellular automata
• Node-searching problem on block graphs
• Interval graphs and searching
• Interval propagation and search on directed acyclic graphs for numerical constraint solving
• A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
• The complexity of minimum-length path decompositions
• On the profile of the corona of two graphs

This page was built for publication: Graph searching and interval completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2706178)