On the public citation graph

Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width

0 signed · 97 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/sapm198981179openalex-snapshot
P4‐Reducible Graphs—Class of Uniquely Tree‐Representable Graphs
inferredcites →https://doi.org/10.1006/jcss.1996.0087openalex-snapshot
Regular Description of Context-free Graph Languages
inferredcites →https://doi.org/10.1007/10692760_27openalex-snapshot
Domination and Steiner Tree Problems on Graphs with Few P 4s
inferredcites →https://doi.org/10.1007/3-540-28788-4openalex-snapshot
Finite Model Theory
inferredcites →https://doi.org/10.1007/3-540-56992-8_19openalex-snapshot
Logical definability of NP-optimisation problems with monadic auxiliary predicates
inferredcites →https://doi.org/10.1007/3-540-60618-1_63openalex-snapshot
On the isomorphism of graphs with few P4s
inferredcites →https://doi.org/10.1007/978-3-540-73671-4_2openalex-snapshot
Computational Complexity
inferredcites →https://doi.org/10.1007/bfb0017474openalex-snapshot
A new linear algorithm for Modular Decomposition
inferredcites →https://doi.org/10.1016/0020-0190(83)90024-8openalex-snapshot
On sparse sets in NP–P
inferredcites →https://doi.org/10.1016/0022-0000(93)90004-gopenalex-snapshot
Handle-rewriting hypergraph grammars
inferredcites →https://doi.org/10.1016/0166-218x(92)90036-aopenalex-snapshot
A tree representation for P4-sparse graphs
inferredcites →https://doi.org/10.1016/0166-218x(92)90180-iopenalex-snapshot
P4-trees and substitution decomposition
inferredcites →https://doi.org/10.1016/0166-218x(94)00012-3openalex-snapshot
Linear time optimization algorithms for P4-sparse graphs
inferredcites →https://doi.org/10.1016/0166-218x(94)90019-1openalex-snapshot
The monadic second order logic of graphs VI: on several representations of graphs by relational structures
inferredcites →https://doi.org/10.1016/0166-218x(94)90026-4openalex-snapshot
k-NLC graphs and polynomial algorithms
inferredcites →https://doi.org/10.1016/0168-0072(95)94698-vopenalex-snapshot
The monadic second-order logic of graphs VIII: Orientations
inferredcites →https://doi.org/10.1016/0196-6774(91)90006-kopenalex-snapshot
Easy problems for tree-decomposable graphs
inferredcites →https://doi.org/10.1016/0304-3975(91)90387-hopenalex-snapshot
The monadic second-order logic of graphs V: on closing the gap between definability and recognizability
inferredcites →https://doi.org/10.1016/0304-3975(93)90064-zopenalex-snapshot
Monadic second-order evaluations on tree-decomposable graphs
inferredcites →https://doi.org/10.1016/0304-3975(94)00272-xopenalex-snapshot
Characterization and complexity of uniformly nonprimitive labeled 2-structures
inferredcites →https://doi.org/10.1016/0304-3975(94)90268-2openalex-snapshot
Monadic second-order definable graph transductions: a survey
inferredcites →https://doi.org/10.1016/0304-3975(95)00016-popenalex-snapshot
A linear-time recognition algorithm for P4-reducible graphs
inferredcites →https://doi.org/10.1016/0304-3975(95)00083-6openalex-snapshot
The monadic second-order logic of graphs X: Linear orderings
inferredcites →https://doi.org/10.1016/0890-5401(90)90043-hopenalex-snapshot
The monadic second-order logic of graphs. I. Recognizable sets of finite graphs
inferredcites →https://doi.org/10.1016/s0049-237x(08)70525-1openalex-snapshot
A Decision Procedure for the Weak Second Order Theory of Linear Order
inferredcites →https://doi.org/10.1016/s0304-3975(96)00220-4openalex-snapshot
On extended P4-reducible and extended P4-sparse graphs
inferredcites →https://doi.org/10.1016/s0304-3975(97)00228-4openalex-snapshot
A partial k-arboretum of graphs with bounded treewidth
inferredcites →https://doi.org/10.1017/9781316717158.019openalex-snapshot
Monadic Second-Order Theories
inferredcites →https://doi.org/10.1112/s0024609396222416openalex-snapshot
FINITE MODEL THEORY (Perspectives in Mathematical Logic)
inferredcites →https://doi.org/10.1137/0221027openalex-snapshot
Recognizing $P_4 $-Sparse Graphs in Linear Time
inferredcites →https://doi.org/10.1137/s0097539793251219openalex-snapshot
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
inferredcites →https://doi.org/10.1142/9789812384720_0005openalex-snapshot
THE EXPRESSION OF GRAPH PROPERTIES AND GRAPH TRANSFORMATIONS IN MONADIC SECOND-ORDER LOGIC
inferredcites →https://doi.org/10.1287/moor.8.2.170openalex-snapshot
A Fast Algorithm for the Decomposition of Graphs and Posets
inferredcites →https://doi.org/10.2307/1971037openalex-snapshot
The Monadic Theory of Order
inferredcites →https://doi.org/10.2307/2273287openalex-snapshot
Modest theory of short chains. I
inferredcites →https://doi.org/10.4064/fm-47-1-57-103openalex-snapshot
The first order properties of products of algebraic systems
inferredcites →https://doi.org/10.4064/fm-49-2-129-141openalex-snapshot
An application of games to the completeness problem for formalized theories
inferredcites →https://doi.org/10.46298/dmtcs.232openalex-snapshot
On P_4-tidy graphs

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.2139/ssrn.4862278openalex-extracted
Weighted Efficient Domination for $S_{1,3,3}$-Free Bipartite Graphs in Polynomial Time
inferred← citeshttps://doi.org/10.2139/ssrn.4862280openalex-extracted
Weighted Efficient Domination for $S_{1,1,5}$-Free Bipartite Graphs in Polynomial Time
inferred← citeshttps://doi.org/10.1002/cpe.3597openalex-snapshot
Incremental computations over strongly distributed databases
inferred← citeshttps://doi.org/10.1007/10719839_14openalex-snapshot
Polynomial Time Recognition of Clique-Width ≤ 3 Graphs
inferred← citeshttps://doi.org/10.1007/11561071_70openalex-snapshot
Greedy Routing in Tree-Decomposed Graphs
inferred← citeshttps://doi.org/10.1007/11917496_6openalex-snapshot
Divide-and-Color
inferred← citeshttps://doi.org/10.1007/3-540-40064-8_19openalex-snapshot
The Tree-Width of Clique-Width Bounded Graphs without Kn,n
inferred← citeshttps://doi.org/10.1007/3-540-44669-9_51openalex-snapshot
On Robust Algorithms for the Maximum Weight Stable Set Problem
inferred← citeshttps://doi.org/10.1007/3-540-46784-x_12openalex-snapshot
NLC2-Decomposition in Polynomial Time
inferred← citeshttps://doi.org/10.1007/3-540-46784-x_14openalex-snapshot
On the Clique—Width of Perfect Graph Classes
inferred← citeshttps://doi.org/10.1007/3-540-48168-0_3openalex-snapshot
Descriptive and Parameterized Complexity
inferred← citeshttps://doi.org/10.1007/978-1-4419-7997-1_81openalex-snapshot
Variations of Dominating Set Problem
inferred← citeshttps://doi.org/10.1007/978-1-4614-6624-6_81-1openalex-snapshot
Variations of Dominating Set Problem
inferred← citeshttps://doi.org/10.1007/978-3-030-39951-1_15openalex-snapshot
Logic-Based Approach to Incremental Monitoring and Optimization on Strongly Distributed Data Streams
inferred← citeshttps://doi.org/10.1007/978-3-030-78163-7_18openalex-snapshot
A Logic-Based Approach to Incremental Reasoning on Multi-agent Systems
inferred← citeshttps://doi.org/10.1007/978-3-032-11835-6_32openalex-snapshot
Polynomial-Time Recognition and Maximum Independent Set in Burling Graphs
inferred← citeshttps://doi.org/10.1007/978-3-319-15579-1_3openalex-snapshot
Hankel Matrices: From Words to Graphs (Extended Abstract)
inferred← citeshttps://doi.org/10.1007/978-3-319-30000-9_36openalex-snapshot
Hankel Matrices for Weighted Visibly Pushdown Automata
inferred← citeshttps://doi.org/10.1007/978-3-540-74208-1_1openalex-snapshot
Approximation Algorithms and Hardness for Domination with Propagation
inferred← citeshttps://doi.org/10.1007/978-3-540-75520-3_2openalex-snapshot
Small Worlds as Navigable Augmented Networks: Model, Analysis, and Validation
inferred← citeshttps://doi.org/10.1007/978-3-642-20877-5_47openalex-snapshot
Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
inferred← citeshttps://doi.org/10.1007/978-3-642-25591-5_65openalex-snapshot
Two Fixed-Parameter Algorithms for the Cocoloring Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-31155-0_13openalex-snapshot
Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths
inferred← citeshttps://doi.org/10.1007/978-3-642-40313-2_49openalex-snapshot
Improved Complexity Results on k-Coloring P t -Free Graphs
inferred← citeshttps://doi.org/10.1007/s002249910009openalex-snapshot
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width
inferred← citeshttps://doi.org/10.1016/j.dam.2010.10.019openalex-snapshot
Characterization and recognition of P4 -sparse graphs partitionable into k independent sets and ℓ cliques
inferred← citeshttps://doi.org/10.1016/j.endm.2004.03.032openalex-snapshot
On -sparse graphs and other families
inferred← citeshttps://doi.org/10.1016/j.ipl.2006.01.007openalex-snapshot
Parameterized power domination complexity
inferred← citeshttps://doi.org/10.1016/s0012-365x(03)00295-4openalex-snapshot
Clique-width of partner-limited graphs
inferred← citeshttps://doi.org/10.1016/s0166-218x(03)00180-xopenalex-snapshot
On variations of P4-sparse graphs
inferred← citeshttps://doi.org/10.1016/s1571-0653(05)80056-3openalex-snapshot
On canonical decomposition of bipartite graphs
inferred← citeshttps://doi.org/10.1016/s1571-0653(05)80146-5openalex-snapshot
Linear time recognition of Weak bisplit graphs
inferred← citeshttps://doi.org/10.1016/s1571-0653(05)80192-1openalex-snapshot
Clique width of Partner limited graphs
inferred← citeshttps://doi.org/10.1016/s1571-0661(04)80191-9openalex-snapshot
GETGRATS
inferred← citeshttps://doi.org/10.1023/b:amai.0000012871.08577.0bopenalex-snapshot
Upper and Lower Bounds on the Complexity of Generalised Resolution and Generalised Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1103/physreva.98.062328openalex-snapshot
Unitary entanglement construction in hierarchical networks
inferred← citeshttps://doi.org/10.1137/06066672xopenalex-snapshot
Approximation Algorithms and Hardness for Domination with Propagation
inferred← citeshttps://doi.org/10.1137/1.9781611975031.176openalex-snapshot
Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
inferred← citeshttps://doi.org/10.1142/s0129054103001625openalex-snapshot
LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P6-FREE GRAPHS
inferred← citeshttps://doi.org/10.1142/s0129054199000368openalex-snapshot
BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION
inferred← citeshttps://doi.org/10.1145/2902251.2902301openalex-snapshot
Tractable Lineages on Treelike Instances
inferred← citeshttps://doi.org/10.1145/3453943openalex-snapshot
Isomorphism, canonization, and definability for graphs of bounded rank width
inferred← citeshttps://doi.org/10.1145/375551.375564openalex-snapshot
The parameterized complexity of database queries
inferred← citeshttps://doi.org/10.1609/aaai.v31i1.10644openalex-snapshot
Going Beyond Primal Treewidth for (M)ILP
inferred← citeshttps://doi.org/10.1609/aaai.v34i05.6201openalex-snapshot
Parameterized Complexity of Envy-Free Resource Allocation in Social Networks
inferred← citeshttps://doi.org/10.20429/tag.2017.000103openalex-snapshot
An Updated Survey on Rainbow Connections of Graphs- A Dynamic Survey
inferred← citeshttps://doi.org/10.2140/mt.2024.3.465openalex-snapshot
How I got to like graph polynomials
inferred← citeshttps://doi.org/10.23638/dmtcs-22-4-8openalex-snapshot
Extension Complexity, MSO Logic, and Treewidth
inferred← citeshttps://doi.org/10.24963/kr.2020/6openalex-snapshot
Symbolic Solutions for Symbolic Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.24963/kr.2022/25openalex-snapshot
Ontology-Mediated Querying on Databases of Bounded Cliquewidth
inferred← citeshttps://doi.org/10.29007/c9f6openalex-snapshot
From SAT to Maximum Independent Set: A New Approach to Characterize Tractable Classes
inferred← citeshttps://doi.org/10.3233/978-1-58603-782-6-261openalex-snapshot
Encounters with A. Mostowski
inferred← citeshttps://doi.org/10.37236/10483openalex-snapshot
Uncountably Many Minimal Hereditary Classes of Graphs of Unbounded Clique-Width
inferred← citeshttps://doi.org/10.37236/2417openalex-snapshot
Locally Identifying Coloring of Graphs
inferred← citeshttps://doi.org/10.46298/dmtcs.2136openalex-snapshot
Improving Vertex Cover as a Graph Parameter
inferred← citeshttps://doi.org/10.46298/dmtcs.2406openalex-snapshot
Tropical Graph Parameters
inferred← citeshttps://doi.org/10.48550/arxiv.0710.2139openalex-snapshot
Approximation algorithms and hardness for domination with propagation
inferred← citeshttps://doi.org/10.48550/arxiv.1106.2772openalex-snapshot
Dominating Induced Matchings for P7-Free Graphs in Linear Time
inferred← citeshttps://doi.org/10.48550/arxiv.1405.2547openalex-snapshot
Finiteness conditions for graph algebras over tropical semirings
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.