The Linkage of a Graph

DOI10.1137/S0097539793255709MaRDI QIDQ4887020zbMATH OpenDBLPWikidataFDO

Authors L. M. Kirousis, Dimitrios M. Thilikos

Publication date 15 October 1996

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

backtrack-free searchconstraint satisfaction problemslinkage of a graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Recommendations

• Graph minors. XXI. graphs with unique linkages
• DAG-width and circumference of digraphs
• The directed 2-linkage problem with length constraints
• Parameterized and Exact Computation
• Disjoint paths in decomposable digraphs

Cited in

(12)

• Graph-links
• Treewidth for graphs with small chordality
• Fugitive-search games on graphs and related parameters
• On the monotonicity of games generated by symmetric submodular functions.
• Edge degeneracy: algorithmic and structural results
• The equivalence chain of a graph
• The Strong Linkage Principle
• Why is maximum clique often easy in practice?
• Linkages in Polytope Graphs
• Fugitive-search games on graphs and related parameters
• Graph coloring via degeneracy in streaming and other space-conscious models
• Online promise problems with online width metrics

This page was built for publication: The Linkage of a Graph

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